递归函数背后的心态

Question

我正在尝试学习递归函数,但我似乎无法理解递归的想法.我已经观看了关于递归和视频教程的视频,但是当我尝试自己解决这些问题时,我无法想到所需的递归.但是,我可以使用循环和迭代很快地解决这些问题.

例如,我看到一个关于查找数字中的位数的问题,答案是:

def digit(n):
  if n < 10:
      return 1
  else:
      return 1 + digit(n/10)

我知道这if是一个递归将停止的点,但我不明白这else部分是如何或为什么工作,即使看了答案.

使用递归函数时,我的思维过程应该是什么样的？

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

以下内容也有所帮助:每次调用该函数时,都会在内存中称为堆栈的内容上堆积一大块本地数据.在这种情况下,该数据块只是参数n,它被存储为局部变量.并且随着调用的每个退出(所以在其中一个返回),这个数据块被从堆栈中取出并丢弃.简洁来说:每个函数调用都有自己的堆栈框架.

拿一些纸,每次调用(见输出),在上面写n并将其放在堆栈上.然后为每个出口扔掉顶部的纸张.虽然这不是灵丹妙药,但它可能有助于你的想象力.

结论:在您的大脑中进行"点击"之前,可能需要相当长的时间.但它确实值得.如果需要一周或更长时间,请不要惊讶.这是正常的,虽然并非所有程序员都会承认这一点.尝试使用我的答案中的输出和一堆纸质笔记逐步执行程序执行.过了一会儿:点击......如果你头晕的话,不要把问题盯住超过四分之一,第二天再试一次(从经验中......).

Python专家的注意事项:Python中的"堆栈"模型只是概念上的,而在例如C++中它是真实的.但它是递归行为的一个很好的模型.