python - 递归函数背后的心态

Question

<分区>

Answer 1

如果手头的问题也是递归的，那么递归就非常有用。一个这样的问题是遍历树状数据结构。任何正在编译的计算机程序都会产生一种称为语法树的结构。编译器遍历树并为找到的分支生成代码。我知道这本身并不能帮助你理解递归，但它只是为了说明递归是一个非常实用的概念。只有给出的例子大多是人为的，因为“真实”的例子需要太多的先验知识。

至于你的例子，一些打印应该清楚发生了什么:

def digit(n):
    print ('Entering "digit" with n == {}'.format (n))

    if n < 10:
        print ('In the "if" now')
        return 1
    else:
        print ('In the "else" now')
        return 1 + digit(n/10)

print (digit (10000))

修改后的代码更加清晰，尝试一步步执行:

def digit(n):
    print ('\nCalling "digit" with n == {}'.format (n))

    if n < 10:
        print ('In the "if" now for n == {}'.format (n))
        result = 1
        print ('Exiting "digit" from the "if" with n == {}, result now is {}'.format (n, result))
        return result
    else:
        print ('In the "else" now for n == {}'.format (n))
        result = 1 + digit(n/10)
        print ('Exiting "digit" with n == {}, result now is {}'.format (n, result))
        return result


print ('Nr of digits is: {}'.format (digit (10000)))

它打印:

D:\aaa>call C:\Python35\python.exe so.py 

Calling "digit" with n == 10000
In the "else" now for n == 10000

Calling "digit" with n == 1000.0
In the "else" now for n == 1000.0

Calling "digit" with n == 100.0
In the "else" now for n == 100.0

Calling "digit" with n == 10.0
In the "else" now for n == 10.0

Calling "digit" with n == 1.0
In the "if" now for n == 1.0
Exiting "digit" from the "if" with n == 1.0, result now is 1
Exiting "digit" with n == 10.0, result now is 2
Exiting "digit" with n == 100.0, result now is 3
Exiting "digit" with n == 1000.0, result now is 4
Exiting "digit" with n == 10000, result now is 5
Nr of digits is: 5

以下内容也有帮助:每次调用该函数时，新的本地数据 block 都会堆积在内存中称为堆栈的东西上。在这种情况下，数据 block 只是作为局部变量存储的参数 n。并且随着调用的每次退出(因此在其中一次返回时)，这 block 数据从堆栈中取出并丢弃。简而言之:每个函数调用都有自己的堆栈框架。

拿几张纸，对于每次调用(见输出)，在上面写下 n 并将其放入堆栈中。然后为每个导出扔掉顶层纸。虽然这不是 Elixir ，但它可以帮助您发挥想象力。

底线:您可能需要相当长的时间才能在大脑中发出“咔哒”声。但这真的很值得。如果需要一周或更长时间，请不要感到惊讶。这很正常，虽然不是所有的程序员都会承认这一点。使用我的答案中的输出和一堆纸质笔记，尝试逐步跟踪程序执行。过了一会儿:点击...如果你头晕，不要盯着问题看超过四分之一，第二天再试(根据经验...)。

Python 专家请注意:Python 中的“堆栈”模型只是概念上的，而在例如C++ 是真实的。但它是递归行为的良好模型。