def is_even(n):
if n == 0:
return True
else:
return is_odd(n-1)
def is_odd(n):
if n == 1:
return True
else:
return is_even(n-1)
is_even(2)
一句话描述我的问题:
上面的
is_even(2)
为什么能够执行?
最近在写一篇文章介绍,但是这块网上介绍的资料比较少,大家有清楚实现细节的吗?
PS :下面文章中有我的分析
上面的代码可以造成死循环,正确的写法如下:
def is_even(n):
if n == 0:
return True
else:
return is_odd(n-1)
def is_odd(n):
if n == 0:
return False
else:
return is_even(n-1)
1
fityme 2016-05-29 23:20:40 +08:00 1
楼主试过 is_even(3) 么?
|
3
JamesRuan 2016-05-30 00:00:20 +08:00 1
不知道实现细节,猜想一下:
从底层的角度来说, is_even 和 is_odd 都是符号,只要执行时,两个符号都存在就行了。 也就是说 Python 的实现应该是扫描了所有的函数定义后绑定了相应的符号。 |
4
clino 2016-05-30 08:47:09 +08:00 1
楼主你应该提出你觉得不能执行的原因 我完全没觉得这有什么不能执行的
|
5
araraloren 2016-05-30 09:04:20 +08:00 1
...这种简单的函数调用有什么不能实现的?
|
6
abcdabcd987 2016-05-30 09:39:12 +08:00 1
这个事情和闭包其实没关系。
在 C 和 C++ 里面要实现这样的功能,必须先在前面把两个函数都给声明了,否则 is_even 会找不到 is_odd 。他们之所以这么做,是因为早期存储能力十分有限,所以编译器尽量做到一趟编译。既然是一趟编译,你就不可能知道在 is_even 之后还有 is_odd 。所以说 C 和 C++ 要实现这样的功能必须得写前向的声明。 后来计算机的存储能力和计算能力都大大加强了,把整个程序存到内存中是轻轻松松的事情,把源程序以不同的形式遍历好几遍也没有任何压力了,所以多趟编译器就流行了。在多趟编译器里面,完全可以第一遍把所有函数的名字和类型扫到符号表里面,于是在第二遍再扫到 is_even 的时候就知道了其实 is_odd 在这个程序里面是有的。 C/C++ 因为历史包袱所以还是保留了前向声明,但是新的语言比如 python ,就不再需要这样麻烦的语法了。 |
7
lcj2class OP @JamesRuan @abcdabcd987
你们说的都是对的,我在文章里面也提到了,这是种通用的技术: https://en.wikipedia.org/wiki/Forward_declaration 我的疑问是, Python 解释器里面是怎么实现这个变量提升( hositing )的呢?( javascript 比较明显,程序员可以感知到) |
8
lcj2class OP |
9
clino 2016-05-30 10:35:02 +08:00 1
@lcj2class 我认为递归里并没有鸡生蛋 蛋生鸡的问题 你想多了
比如在一个 function test 里调用 test 函数,你认为这里有这个问题吗? |
10
abcdabcd987 2016-05-30 10:50:43 +08:00 via iPhone 1
@lcj2class 你这个例子里面没有提现到变量提升的问题吧?另外我觉得变量提升应该只是 JavaScript 的处理方法而已
|
11
araraloren 2016-05-30 13:02:04 +08:00 1
@lcj2class 。。变量提升不了解,稍微搜索看了下,就是作用域的问题吧,递归并不存在你说的 鸡**蛋**鸡 问题
|
12
fy 2016-05-30 13:05:29 +08:00 1
LZ 想多了,你以为 Python 中的函数调用是什么行为?
因为函数在 Python 中是第一类对象,随时可以声明和引用,又有__new__和__call__这种东西捣乱,所以函数调用行为是根本无法预测的。那怎么办?那就不预测呗。 is_even(n-1) 翻译后代码的实际含义是:从变量表中找一个名叫 is_even 的对象,并调用它。 注意!查找和调用行为都是在运行时完成的,也就是代码编译完成之后! 所以在你 is_even(2) 的时候,一切都已经准备好了。 >>> import dis >>> dis.dis('func()') 1 0 LOAD_NAME 0 (func) 3 CALL_FUNCTION 0 (0 positional, 0 keyword pair) 6 RETURN_VALUE >>> dis.dis('is_even(2)') 1 0 LOAD_NAME 0 (is_even) 3 LOAD_CONST 0 (2) 6 CALL_FUNCTION 1 (1 positional, 0 keyword pair) 9 RETURN_VALUE >>> 就这么简单 |
13
fy 2016-05-30 13:08:17 +08:00 1
说白了编译到 is_even(...) 的时候根本就不关心 is_even 是否存在。多大点事么,查表调用就是了。
|
14
lcj2class OP |
15
JamesRuan 2016-05-30 15:41:41 +08:00
@lcj2class 如果你的理解仅仅停留在解释器按语法树扫描的同时执行,就会有这类疑问。
函数式编程里面是用 Y combinator 做这个的事情的,多重递归就用 multiple Y combinator 。 然而实际的硬件层面最便捷的就是查表。你可以理解成解释器先扫描一遍源代码,把函数调用转变成符号跳转( python 中是字节码),然后再执行具体字节码。 |
16
yamada 2016-05-30 16:23:26 +08:00 1
初学,借地问一下
db = SQLAlchemy() class userinfo(db.Model): pass userinfo 类的继承,这种写法是什么意思?还能继承一个运行时才有的属性? |
17
lcj2class OP @yamada
https://docs.python.org/3/tutorial/classes.html > As is true for modules, classes partake of the dynamic nature of Python: they are created at runtime, and can be modified further after creation |