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

[lcj2class]

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)

[fityme]

楼主试过 is_even(3) 么？

[lcj2class]

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

[JamesRuan]

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

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

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

[clino]

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

[araraloren]

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

[abcdabcd987]

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

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

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

[lcj2class]

@JamesRuan @abcdabcd987

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

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

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

[lcj2class]

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

[clino]

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

[abcdabcd987]

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

[araraloren]

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

[fy]

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

就这么简单

[fy]

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

[lcj2class]

@fy @araraloren @abcdabcd987 @clino

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

[JamesRuan]

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

[yamada]

初学，借地问一下

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

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

[lcj2class]

@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