递归算法
递归函数的条件
一般来说，递归需要边界条件，整个递归的结构中要有递归前进段和递归返回段。当边界条件不满足，递归前进，反之递归返回。就是说递归函数一定需要有边界条件来控制递归函数的前进和返回。
内存栈区堆区
栈区空间就是我们常说的栈，栈是一个有去有回，先进后出后出的空间，就像我们上面的例子中讲的，我们最先执行的是函数的第一次调用，但是第一次调用却是最后执行释放掉的，而第十一次调用是最后调用，最先执行释放掉的，这就是先进后出。与栈空间概念相违背的是队列空间，队列空间是一个有去有回，先进先出的空间，就像我们平时排队一样，先排队的会比后来的人先买到票。 单独的讲栈堆就是一种数据结构，栈是先进后出的一种数据结构，堆是排序后的一种树状数据结构。 栈区堆区是内存空间，栈区就是按照先进后出的数据结构，无论创建或销毁都是自动为数据分配内存，释放内存，这是系统自动创建的；堆区就是按照排序后的树状数据结构，可优先取出必要的数据，无论创建或者销毁都是手动分配内存，释放内存，这是编程工作者手动编程出来的。 运行程序时在内存中执行，会因为数据类型的不同而在内存的不同区域运行，因不同语言对内存划分的机制不一，当大体来说，有如下四大区域： 栈区：分配局部变量空间； 堆区：是用于手动分配程序员申请的内存空间； 静态区：又称之为全局栈区，分配静态变量，全局变量空间； 代码区：又称之为只读区、常量区，分配常量和程序代码空间；
尾递归
在函数返回的时候，调用其本身，并且return语句不包含表达式，这样的一个递归函数就是一个尾递归函数。
关于return
首先要理解return,return有三层含义：
返回值是什么
返回到调用该层函数体的位置
返回到上一级
其次要理解print,print打印的是函数的返回值,如果一个函数没有返回值，则打印None
最后，要清楚只有return代表函数的返回值，赋值语句并不代表，仅代表函数内部多了一个变量而已。
理解print
#例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：
def a(n):
if n<=1:
return 1
a(n-1) #loc
print(a(3))
# 输出
None
上面的例子可以用下面的图来理解:
依照上面的分析print打印的是返回值，所以本题找出a（3）的返回值皆可，从图中①部分可以看出a(3)的返回值为None，所以最终结果为None，可以直接得到结果，但是函数运行到这里没有结束，由于是递归函数，为了深入理解，现全过程的分析一下递归的过程。
递去
过程①：首先执行过程①函数体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 1
print(n)
return a(n-1)-1 #loc
print(a(3)))
# 输出
3
2
-1
例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 1
b=a(n-1) #loc
print(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）的返回值。
python递归函数基本原理及执行顺序
代码示例1
def test(n: int) -> None:
print("test", n)
if n == 0:
print("over")
else:
test(n - 1)
print("test***", n)
执行结果:
test 4
test 3
test 2
test 1
test 0
over
test*** 0
test*** 1
test*** 2
test*** 3
test*** 4
print(”test”, n)调用时执行 print(”test***”, n)在递归调用之后，待递归结束，栈帧逐个退出时执行
代码示例2
def digital_number_root(n: int) -> int:
single_number_list = [int(i) for i in str(n)]
total = sum(single_number_list)
if total >= 10:
return digital_number_root(total)
return total
使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。