V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
lcj2class
V2EX  ›  Python

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

  •  
  •   lcj2class · 2016-05-29 23:02:01 +08:00 · 3256 次点击
    这是一个创建于 3086 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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
        1
    fityme  
       2016-05-29 23:20:40 +08:00   ❤️ 1
    楼主试过 is_even(3) 么?
    lcj2class
        2
    lcj2class  
    OP
       2016-05-29 23:41:46 +08:00   ❤️ 1
    @fityme
    我实现的时候有点错误,追加里面已经更正了。
    JamesRuan
        3
    JamesRuan  
       2016-05-30 00:00:20 +08:00   ❤️ 1
    不知道实现细节,猜想一下:

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

    也就是说 Python 的实现应该是扫描了所有的函数定义后绑定了相应的符号。
    clino
        4
    clino  
       2016-05-30 08:47:09 +08:00   ❤️ 1
    楼主你应该提出你觉得不能执行的原因 我完全没觉得这有什么不能执行的
    araraloren
        5
    araraloren  
       2016-05-30 09:04:20 +08:00   ❤️ 1
    ...这种简单的函数调用有什么不能实现的?
    abcdabcd987
        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 ,就不再需要这样麻烦的语法了。
    lcj2class
        7
    lcj2class  
    OP
       2016-05-30 10:17:02 +08:00   ❤️ 1
    @JamesRuan @abcdabcd987

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

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

    我的疑问是, Python 解释器里面是怎么实现这个变量提升( hositing )的呢?( javascript 比较明显,程序员可以感知到)
    lcj2class
        8
    lcj2class  
    OP
       2016-05-30 10:29:43 +08:00   ❤️ 1
    @clino @araraloren
    你们说的简单,应该是形式上的简单吧?你们不觉得解释器在处理递归调用时,这里面有鸡生蛋,蛋生鸡的问题嘛?
    clino
        9
    clino  
       2016-05-30 10:35:02 +08:00   ❤️ 1
    @lcj2class 我认为递归里并没有鸡生蛋 蛋生鸡的问题 你想多了
    比如在一个 function test 里调用 test 函数,你认为这里有这个问题吗?
    abcdabcd987
        10
    abcdabcd987  
       2016-05-30 10:50:43 +08:00 via iPhone   ❤️ 1
    @lcj2class 你这个例子里面没有提现到变量提升的问题吧?另外我觉得变量提升应该只是 JavaScript 的处理方法而已
    araraloren
        11
    araraloren  
       2016-05-30 13:02:04 +08:00   ❤️ 1
    @lcj2class 。。变量提升不了解,稍微搜索看了下,就是作用域的问题吧,递归并不存在你说的 鸡**蛋**鸡 问题
    fy
        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
    >>>

    就这么简单
    fy
        13
    fy  
       2016-05-30 13:08:17 +08:00   ❤️ 1
    说白了编译到 is_even(...) 的时候根本就不关心 is_even 是否存在。多大点事么,查表调用就是了。
    lcj2class
        14
    lcj2class  
    OP
       2016-05-30 13:43:49 +08:00   ❤️ 1
    @fy @araraloren @abcdabcd987 @clino

    确实是我想多了,一时糊涂没搞清楚 Python 解释器编译时与运行时行为的区别,谢谢大家了。
    JamesRuan
        15
    JamesRuan  
       2016-05-30 15:41:41 +08:00
    @lcj2class 如果你的理解仅仅停留在解释器按语法树扫描的同时执行,就会有这类疑问。
    函数式编程里面是用 Y combinator 做这个的事情的,多重递归就用 multiple Y combinator 。
    然而实际的硬件层面最便捷的就是查表。你可以理解成解释器先扫描一遍源代码,把函数调用转变成符号跳转( python 中是字节码),然后再执行具体字节码。
    yamada
        16
    yamada  
       2016-05-30 16:23:26 +08:00   ❤️ 1
    初学,借地问一下

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

    userinfo 类的继承,这种写法是什么意思?还能继承一个运行时才有的属性?
    lcj2class
        17
    lcj2class  
    OP
       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
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2690 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 10:07 · PVG 18:07 · LAX 02:07 · JFK 05:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.