什么是函数的递归

如果一个函数在它自身的函数体内调用自身,我们就可以把这样的函数称为递归函数。

举个简单栗子

def fun():
  print("我也太好看惹!")
  fun()

fun()

定义一个函数 fun(),在函数体中输出一行字符串,紧接着又在后面调用它自己,这就构造了一个最简单的递归函数

跑一下上面的代码,控制台会无限输出 "我也太好看惹" 这句话,这显然是不合理的,如果一直调用下去将会导致栈溢出。所以在使用递归函数时我们需要给它设置结束条件,也就是所谓的 "墙",当函数递归到某一层时,遇到墙结束递归,然后返回。可以对代码做如下修改:

def fun(i):
  i += 1    #每次调用 fun() , i自加1
  print("我也太好看惹!")
  if i < 10:
    fun(i)
  else:
    print("好看太多了!")

fun(0)

函数输出 10行 "我也太好看惹!" 以后停止递归,然后输出 "好看太多了!"。

递归的返回值问题

# 定义一个自加函数
def count(n):
  n += 1   # n++
  if n < 5:
    count(n)  # 调用自身,即函数递归
  else:
    return n

res = count(0)
print(res)  # 期望结果 res = 5,实际 res = none

在搞清什么是递归函数之后,我们再来看上面这个栗子。
函数接收参数 n,每次调用 n 自加 1,经过四次递归,我们期望得到的结果为 5,乍一看貌似没什么问题,而实际运行结果却为 none。为了整明白返回值 none 的原因,我们还得理解 函数栈 的概念。

函数栈

顾名思义,函数在调用时也遵循 "先入后出" 的规则,最先入栈的函数会被压入栈底。就好比手枪弹夹,一段内存就是一个弹夹,一个函数就是一颗子弹,每次递归相当于把子弹压入弹夹中。但压入的子弹是有限制的,也就是弹夹容量是有上限的,如果调用次数超过系统分配的内存上限时,就会出现前面说的栈溢出问题。栈溢出 等于 弹夹炸了

咳咳,也就是说,我们调用递归的过程类似给手枪上弹的过程,我们可以简单分析下前面那个栗子的调用顺序:

fun(0) -> fun(1) -> fun(2) -> fun(3) -> fun(4)

我们会发现前四次调用均无返回值,直到第五次递归开始,变量 n = 5,条件分支跳转到 else,return n 表示把 n 返回给上一层,关键来了,因为上一层 fun(3) 中并没有返回值,所以 n 就变成了 none,同理,fun(2) 、 fun(1) 和 fun(0) 的返回值也就变成了 none。返回顺序:

fun(0) <- fun(1) <- fun(2) <- fun(3) <- fun(4)

理解了问题所在,于是我们可以做如下修改:

def count(n):
  n += 1
  if n < 5:
    return count(n)  #加一个 return
  else:
    return n

res = count(0)
print(res)  # res = 5

每次调用递归时,return 自己,内层把返回值返回给外层,这样当最内层的返回值 5 就能返回给最外层,从而得到我们想要的结果。