最近在做递归一些相关的东西，发现递归入门很容易，但要具体了解其实现过程，比较难以理解，在这里将自己这几天的摸索记录一下，写知乎的主要目的是为了给自己做笔记，在做笔记的同时，帮助后来人少走弯路。今天简要的介绍下递归具体实现过程，后面我会加入具体一些递归算法(排序、二叉树等)的分析。

一、引子

要理解递归，首先要理解return，return有三层含义：1、返回值是什么；2、返回到调用该层函数体的位置；3、返回到上一级（上一层）。其次要理解print，print打印的是函数的返回值，如果一个函数没有返回值，打None。最后，要清楚，只有return代表函数的返回值，赋值语句并不代表，仅代表函数内部多了一个变量而已（见例6）

• 首先看个例子理解print
• 例1：

#例1：
def a(n):print(n) 
print(a(3))
'''

输出：

3
None

函数体a中没有return，也即没有返回值，所以在执行a（3）时，先执行函数内部的print，打印3，然后执行print(a(3))，而a（3）这个函数没有返回值，所以输出None。

• 例2

def a(n):print(n) return
print(a(3))

输出：

3
None

函数体a中有return，但是return后面没有值，也即没有返回值，所以在执行a（3）时，先执行函数内部的print，打印3，然后执行print(a(3))，而a（3）这个函数没有返回值，所以输出None。

• 例3

def a(n):print(n) return 2
print(a(3))

输出：

3
2

本例找出a（3）的返回值即可。函数体a中有return，、return后面返回2，所以在执a（3）时，先执行函数内部的print，打印3，然后执行print(a(3))，打印a(3)的返回值，所以输出2。

二、递归

继续看实际的的递归案例，递归包括两个过程：1、递去；2、回归。一般递去的过程容易理解，而让人苦恼的是回归的过程难以理解，接下来带领大家分析一下。首先看一个例子。

例4和例5主要是为了让大家理解回归的过程以及函数返回值，例6中将递归调用函数赋值给了一个变量，主要是为了理解return和赋值的区别。

• 例4

def a(n):if n<=1:return 1a(n-1)  #loc
print(a(3))

输出：

None

上面的例子可以用下面的图来理解：

例4执行过程

依照上面的分析print打印的是返回值，所以本题找出a（3）的返回值皆可，从图中①部分可以看出a(3)的返回值为None，所以最终结果为None，可以直接得到结果，但是函数运行到这里没有结束，由于是递归函数，为了让大家深入理解，现全过程的分析一下递归的过程。

要求最外层函数a（3）的返回值需先向最内层函数递进（图从①到③），然后从最内层函数向外回归（图从③到①），回到最外层才能找到返回值，所以要进行递归的两个过程，递去和回归的两个过程分析。现具体分析一下原理。

递去：

过程①：首先执行过程①函数体a(3)，a(3)没有返回值（返回值为None），但是会调用a(3-1)，也即a(2)，此时函数执行还没有结束，因为出来了新的函数a(2)，a(2)的结果还不知道，仅仅知道a(3)的函数体中调用了a（2）这个未知函数，此时a(3)还没有执行完毕，a(3)这个函数体要执行完毕，必须要去执行a（2）；

过程②：继续执行过程②的函数体a(2)，没有返回值（返回值为None），调用a(2-1)，也即a(1)。此时函数执行也还没有结束，因为出来了新的函数a(1)，a(1)的结果还不知道，仅仅知道a(2)的函数体中调用了a（1）这个未知函数，此时a(2)还没有执行完毕，a(2)这个函数体要执行完毕，必须要去执行a（1）；

过程③：继续执行过程①的函数体a(1)，进入到if语句内，返回值为1。在这个过程中，在执行a(1)的时候具有返回值1，a(2)、a(3)均没有返回值，因为只有a(1)进入到if语句中，而且其中包含return 1 ，说明最终a(1)返回值为1，也即a(1)与1指向同一块地址。

回归：

过程③：遇到return，要看return的三层含义：

1、返回值，也就是1；

2、返回到调用该函数的位置，也就是loc行，也即过程②中的a(1)那行语句；

3、返回到上一级，这个怎么看？先看本层，再看调用谁会产生本层函数体，那么他就是本层函数体的上一层。首先本层函数体的名字为a(1)，那么调用谁会产生a(1)呢？，也就是调用过程②的函数体a(2)，会产生a（1），在细致一点返回的是过程②的哪一行呢？也就是过程②的行a(1)。此时过程②的a(1)指向过程③中1的地址。可以广义理解为a(1)的返回值就是1。 因此过程②就是过程③的上一级，因为运行过程②才会产生过程③。

过程②：原函数在执行到函数体a（2）的时候，是没有return，可以改写成return None，也就是可以这么理解，任何函数必须要有返回值，只是None可以忽略不写。

现在过程②函数体的执行结果是多少，就是要找到其返回值，就是None，跟中建那句a(1)没有什么关系，a(1)仅仅是指向了过程③的的函数体

过程③：同过程②，a(2)仅仅是指向了过程②的的函数体

按照这个思路，重新整理下，a(1)返回值为1，紧接着，返回上一级这就是a(2)，a(2)无返回值（返回值为None），紧接着逐级返回到a(3)，a(3)无返回值（返回值为None）。

• 例5

def a(n):if n<=1:return 1print(n)return a(n-1)-1  #loc
print(a(3))

输出：

3
2
-1

例5的执行过程为：

例5原理图

同样，找出a（3）的返回值即可，本例不同于例4，返回值不能直接看出来，需要进行递去和回归的两个过程分析。

递去：

过程①：执行a(3)函数体的时候，首先打印3，然后本层函数返回值为a(2)-1,要想知道a(3)的结果，就必须其求得返回值中a(2)的结果，所以函数体a(3)还没有执行完，就要去执行函数体a(2)了，这就注定了要有回的过程，当求得a(2)代入返回值中，才能求得a(3)；

过程②：执行a(2)的时候，首先打印2，然后返回a(1)-1,同理，函数体a(2)还没有执行完，就要去执行函数体a(1)了，这就注定了要有回的过程，当求得a(1)代入返回值中，才能求得a(2)；

过程③：执行a(1)的时候，进入到if语句中，返回值为1。但是注意看过程③，原函数中return 1后面的东西我没有写，因为函数执行遇到return就会结束，后面的语句不会执行。也即不会打印出1。然后求得a(1)之后，需要逐级返回，代入之前未执行完毕的函数中。

所以本例a(3)返回值为a(2)-1，a(2)返回值为a(1)-1，a(1)返回值为1。a(3)还没有执行完就返回了a(2)-1，而a(2)还没有执行完就返回了a(1)-1，a(1)返回了1，上面两层函数a(3)、a(2)还没有执行完，所以要返回外层函数，将外层函数执行完，整个函数调用才算结束。

回归：

过程②是过程③的上一级，过程①是过程②的上一级，一级一级逐级回归。

过程③：我们看下return的三层含义：

1、返回值为1；

2、调用该函数体的位置，就是loc位置（过程2中的return a(1)-1这个语句）；

3、返回到上一级，为了找出上一级，先看本级，谁返回的1，就是该层函数体，也即a（1）；那么调用谁会产生a(1)，就是a（2-1）.所以递归终止条件的return首先返回的是a(1)的上一级，也即a(2-1)的这级语句，而谁产生的a(2-1),也就是a(2)函数体。也就是过程②。

过程②：看一个函数的执行结果，就要看该函数的返回值是多少?过程②的函数体a(2)返回值就看return语句，也就是a(1)-1=0

过程①:过程①中函数体a(3)的返回值为a(2)-1=0-1=-1,而在调用该函数的时候用了print(a(3))，print打印的是函数的返回值，所以最后还需要输出a(3)的返回值为-1.

• 例6

def a(n):if n<=1:return 1b=a(n-1)  #locprint(b)
print(a(3))

输出：

1
None
None

例6的执行过程为：

本例也是找出a(3)的返回值即可。但是在本例中我将a(n-1)赋值给了变量b，这个跟前面有什么不一样呢？_

递去：

过程①：首先执行函数体a(3)，a（3）没有返回值（返回值为None），但是会调用a（3-1），也即a（2）,然后将a(2)的值赋值给b，a(2)是一个函数，不是一个具体的值，所以b=a(2)下面的语句不会执行，要等计算出a(2)这个函数之后，才会反过来执行下面的函数。

过程②：继续执行a（2），没有返回值，调用a（2-1），也即a（1）；

过程③：继续执行a（1），进入到if语句内，返回值为1。

注意：在递去的过程没有执行一次print，因为print在函数的后面，在回归的过程才会执行。

回归：

过程③：执行函数体a（1）时，遇到return，这里不给大家具体分析了，a(1)的返回值为1。

过程②：直接利用上面的分析结论，返回到上一层a（1）的上一级函数体a（2），语句为a(2-1)，但是这里不一样的是多了一个赋值语句，什么意思呢？意思就是将a(2-1)即a(1)的返回值幅值给变量b，也就是b和a(1)指向同一块内存地址，因为a(1)的返回值为1，所以执行过程②的函数体a(2)时，所以b=1，紧接着打印将b打印出来。《注意：此时将函数体a(1)的返回值1赋值给函数体a(2)中的b，并不是意味着a(2)具有返回值b，因为返回值只能通过return语句来标记，赋值的语句仅仅是声明在a(2)函数体中有个一个变量b，而这个变量b就是a(1)的返回值，并在之后将其打印》所以此时第一次返回时，返回a（2），打印1；

过程①：然后继续返回上一层过程①，a（2）的上一层函数为a（3），执行函数体a(3)，首先函数体内部将a(2)赋值给b，a（2）是多少？要看a（2）是多少，就要找到a(2)的返回值，看过程②，返回值为None，所以b=None。接下来打印第一个None。最后还有一个None是怎么产生的呢？就是print(a(3))再次打印了a（3）的返回值。