1 前言

递归函数的概念很简单，就是函数调用本身。但在实际接触递归函数时，往往不知道怎么下手，在其中碰到的问题也不知道如何解决，比如明明可以print却无法return有效值，根本原因就是不知道递归函数在运行时的具体情况，借着这篇文章，来看看递归函数究竟是怎么回事吧。

2 案例解析

以常见的斐波拉契数列为例，第n项斐波拉契数等于第n-1项和第n-2项斐波拉契数的和。通过一个for循环就能轻易的得到第n项斐波拉契数。

fl=1 fn=1 for i in range(3,n+1):     mid=fl     fl=fn     fn=fl+mid print(fn)

如果换成递归函数，其实也不难，但是你真的能理解这个递归函数的运行流程吗？

def fib(n):    if n==1 or n==2 :        return 1    return fib(n-1)+fib(n-2)

首先得知道，递归函数是先调用后执行。以上述fib()函数为例，求第5项斐波拉契数列，来看看递归函数的执行过程。

图1 函数调用过程

fib()函数会沿着红色箭头一直调用到能够执行到递归出口的函数，也就是当n等于1或者2时，此时并没有执行任何数值计算，只是在不停的调用子函数。当执行到递归出口时，才得到第一项和第二项斐波拉契的值，并向上返回。

图二中蓝色箭头表示函数的调用过程，红色箭头表示递归函数在递归出口得到值后，不断的往上一层递归函数返回值。

图2 代码执行流程

当n=5会执行fib(4)和fib(3)…，而当n=1或者2时，会执行fib()函数中if下的语句，也就是递归出口，return 1 ，当函数执行return语句时表明函数执行结束，返回结果1。

但在这个递归函数中，执行fib(5)会得到1吗？很明显不会，那这个1去哪了，不应该直接返回，然后结束函数吗？

很明显这个1并不是fib(5)的递归出口，这个1被返回给了上一层函数。以fib(3)为例：

当n=3时，执行return fib(2)+fib(1)，fib(2)和fib(1)会直接返回1，返回的1便到了这里。变为了 return 1+1 。fib(3)则会继续将2返回给fib(4)，fib(4)接收到fib(3)和fib(2)返回的2和1得到3，并返回给fib(5)。

3 问题分析

这也解释了为什么很多人在使用递归函数时，return的值为None，但在return前print却有值的问题。因为你只在函数最后一层return，这个return只会将值返回给函数上一层。如果需要将值返回调用，那么每一层函数都得有return并且被执行。

4 结论

递归函数在编程中是很实用和常见的 ”工具” ，明白了递归函数的执行过程，对于算法的学习有很大的好处。下一篇文章来看看怎么使用递归函数并结合DFS算法实现全排列吧。

END

主  编   |   王文星

责  编   |   马原涛

 where2go 团队

---

   

微信号：算法与编程之美          

长按识别二维码关注我们!

温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！