谈一谈|return None来看递归函数流程解析

 

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项斐波拉契数列,来看看递归函数的执行过程。

谈一谈|return None来看递归函数流程解析

图1 函数调用过程

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

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

谈一谈|return None来看递归函数流程解析

图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 团队


   

微信号:算法与编程之美          

谈一谈|return None来看递归函数流程解析

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

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

上一篇:Summary on deep learning framework --- Torch7


下一篇:栈和递归---斐波那契数列的非递归实现