Python 中的间接递归调用是怎么实现的？

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 ：下面文章中有我的分析

编程语言中的变量作用域与闭包

第 1 条附言 · 2016-05-29 23:41:13 +08:00

上面的代码可以造成死循环，正确的写法如下：

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)

17 条回复 • 2016-05-31 12:03:28 +08:00

fityme

2016-05-29 23:20:40 +08:00

楼主试过 is_even(3) 么？

lcj2class

2016-05-29 23:41:46 +08:00

@fityme
我实现的时候有点错误，追加里面已经更正了。

JamesRuan

2016-05-30 00:00:20 +08:00

不知道实现细节，猜想一下：

从底层的角度来说， is_even 和 is_odd 都是符号，只要执行时，两个符号都存在就行了。

也就是说 Python 的实现应该是扫描了所有的函数定义后绑定了相应的符号。

clino

2016-05-30 08:47:09 +08:00

楼主你应该提出你觉得不能执行的原因我完全没觉得这有什么不能执行的

araraloren

2016-05-30 09:04:20 +08:00

...这种简单的函数调用有什么不能实现的？

abcdabcd987

2016-05-30 09:39:12 +08:00

这个事情和闭包其实没关系。

在 C 和 C++ 里面要实现这样的功能，必须先在前面把两个函数都给声明了，否则 is_even 会找不到 is_odd 。他们之所以这么做，是因为早期存储能力十分有限，所以编译器尽量做到一趟编译。既然是一趟编译，你就不可能知道在 is_even 之后还有 is_odd 。所以说 C 和 C++ 要实现这样的功能必须得写前向的声明。

后来计算机的存储能力和计算能力都大大加强了，把整个程序存到内存中是轻轻松松的事情，把源程序以不同的形式遍历好几遍也没有任何压力了，所以多趟编译器就流行了。在多趟编译器里面，完全可以第一遍把所有函数的名字和类型扫到符号表里面，于是在第二遍再扫到 is_even 的时候就知道了其实 is_odd 在这个程序里面是有的。 C/C++ 因为历史包袱所以还是保留了前向声明，但是新的语言比如 python ，就不再需要这样麻烦的语法了。

lcj2class

2016-05-30 10:17:02 +08:00

@JamesRuan @abcdabcd987

你们说的都是对的，我在文章里面也提到了，这是种通用的技术：

https://en.wikipedia.org/wiki/Forward_declaration

我的疑问是， Python 解释器里面是怎么实现这个变量提升（ hositing ）的呢？（ javascript 比较明显，程序员可以感知到）

lcj2class

2016-05-30 10:29:43 +08:00

@clino @araraloren
你们说的简单，应该是形式上的简单吧？你们不觉得解释器在处理递归调用时，这里面有鸡生蛋，蛋生鸡的问题嘛？

clino

2016-05-30 10:35:02 +08:00

@lcj2class 我认为递归里并没有鸡生蛋蛋生鸡的问题你想多了
比如在一个 function test 里调用 test 函数,你认为这里有这个问题吗?

abcdabcd987

2016-05-30 10:50:43 +08:00 via iPhone

@lcj2class 你这个例子里面没有提现到变量提升的问题吧？另外我觉得变量提升应该只是 JavaScript 的处理方法而已

araraloren

2016-05-30 13:02:04 +08:00

@lcj2class 。。变量提升不了解，稍微搜索看了下，就是作用域的问题吧，递归并不存在你说的鸡**蛋**鸡问题

2016-05-30 13:05:29 +08:00

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
>>>

就这么简单

2016-05-30 13:08:17 +08:00

说白了编译到 is_even(...) 的时候根本就不关心 is_even 是否存在。多大点事么，查表调用就是了。

lcj2class

2016-05-30 13:43:49 +08:00

@fy @araraloren @abcdabcd987 @clino

确实是我想多了，一时糊涂没搞清楚 Python 解释器编译时与运行时行为的区别，谢谢大家了。

JamesRuan

2016-05-30 15:41:41 +08:00

@lcj2class 如果你的理解仅仅停留在解释器按语法树扫描的同时执行，就会有这类疑问。
函数式编程里面是用 Y combinator 做这个的事情的，多重递归就用 multiple Y combinator 。
然而实际的硬件层面最便捷的就是查表。你可以理解成解释器先扫描一遍源代码，把函数调用转变成符号跳转（ python 中是字节码），然后再执行具体字节码。

yamada

2016-05-30 16:23:26 +08:00

初学，借地问一下

db = SQLAlchemy()
class userinfo(db.Model):
pass

userinfo 类的继承，这种写法是什么意思？还能继承一个运行时才有的属性？

lcj2class

2016-05-31 12:03:28 +08:00

@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