递归函数

什么是递归函数

如果一个函数，可以自己调用自己，那么这个函数就是一个递归函数。

递归，递就是去，归就是回，递归就是一去一回的过程。

递归函数的条件

一般来说，递归需要边界条件，整个递归的结构中要有递归前进段和递归返回段。当边界条件不满足，递归前进，反之递归返回。就是说递归函数一定需要有边界条件来控制递归函数的前进和返回。

定义一个简单的递归函数

# 定义一个函数
def recursion(num):
	
    print(num)
	if num == 0:
		return "ok"
	
    # 这个函数在自己的作用域中调用自己，这个函数就是一个递归函数
	recursion(num-1)


recursion(10)
"""
结果：
10
9
8
7
6
5
4
3
2
1
0
"""

代码解析

我们执行这个函数，参数给了一个10，但是这个函数执行的过程中，又调用了自己，所以现在这个函数就会进入先执行第二次调用自己的过程中，第一次的调用就暂时的阻断了；

第二次调用的时候，num-1，参数就变成了9，继续执行，然后就又执行到了调用自己的代码中，现在就会执行第三次调用的过程中，第二次的调用也阻断了；

这就是 递 的过程；

…………

第十一次调用的时候，num-1，层层的嵌套，参数就变成了0，就符合了作用域中的if num == 0的条件判断式，第十一次的调用就没有再执行到了调用自己的代码，而是彻彻底底的执行完成了 ，然后代码的执行就又回到了第十次的函数调用中。

第十次的函数调用阻断的时候是执行到了recursion(num-1)，但是这一行代码执行完了，也就是第十一次调用执行完了，并且后面也没有任何代码，所以第十次调用也结束了，然后就回到了第九次调用；然后第八次；再就是第七次，一直到第一次结束，整个函数的执行就结束了；

这就是 归 的过程。

内存栈区堆区

栈区空间就是我们常说的栈，栈是一个有去有回，先进后出后出的空间，就像我们上面的例子中讲的，我们最先执行的是函数的第一次调用，但是第一次调用却是最后执行释放掉的，而第十一次调用是最后调用，最先执行释放掉的，这就是先进后出。与栈空间概念相违背的是队列空间，队列空间是一个有去有回，先进先出的空间，就像我们平时排队一样，先排队的会比后来的人先买到票，之后我们学习并发的时候，我们会详细的讲述队列的概念。

单独的讲栈堆就是一种数据结构，栈是先进后出的一种数据结构，堆是排序后的一种树状数据结构。

栈区堆区是内存空间，栈区就是按照先进后出的数据结构，无论创建或销毁都是自动为数据分配内存，释放内存，这是系统自动创建的；堆区就是按照排序后的树状数据结构，可优先取出必要的数据，无论创建或者销毁都是手动分配内存，释放内存，这是编程工作者手动编程出来的。

运行程序时在内存中执行，会因为数据类型的不同而在内存的不同区域运行，因不同语言对内存划分的机制不一，当大体来说，有如下四大区域：

1. 栈区：分配局部变量空间；
2. 堆区：是用于手动分配程序员申请的内存空间；
3. 静态区：又称之为全局栈区，分配静态变量，全局变量空间；
4. 代码区：又称之为只读区、常量区，分配常量和程序代码空间；

上面的栈区、读取、静态区、代码区都只是内存中的一段空间。

死递归

所以我们在使用递归函数的时候要注意，递归函数调用的过程就是一个开辟栈和释放栈的过程，调用的时候开辟栈空间，结束的时候释放栈空间，所以说，如果开辟的空间不结束就会一直存在，就会一直占用内存空间，但是栈空间是一个先进后出的空间，如果新开启的空间不释放掉，之前的空间也不会释放掉的，那么如果我们开辟的空间很多很多，但是又释放不掉，那么我们弱小的内存是否有足够的空间容纳得下这么多的栈呢？如果容纳不下，那么我们的计算机就会爆炸，所以我们在使用递归的时候要注意避免这种情况。尤其是死递归。

每次调用函数时，在内存宗都会单独开辟一个空间，配合函数运行，这个空间叫做栈帧空间。

1、递归是一去一回的过程，调用函数时，会开辟栈帧空间，函数执行结束之后，会释放栈帧空间，递归实际上就是不停地开辟和释放栈帧空间的过程，每次开辟栈帧空间，都是独立的一份，其中的资源不共享。

2、触发回的过程当最后一层栈帧空间全部执行结束的时候，会触底反弹，回到上一层空间的调用处，遇到return，会触底反弹，回到上一层的调用处

3、写递归时，必须给予递归跳出的条件，否则会发生内存溢出，可能会出现死机的情况，所以当递归的层数过多的时候，不建议使用递归。

Python中的环境递归的层数默认为1000层左右，一般都是996层。

# 下面的递归函数没有跳出递归的条件，所以是一个死递归，执行看，是不是1000左右。
def recursion(num):
	print(num)
	recursion(num+1)

recursion(1)

尾递归

简单的来说，在函数返回的时候，调用其本身，并且return语句不包含表达式，这样的一个递归函数就是一个尾递归函数。

换句话说返回的东西就是函数本身就是尾递归函数，而递归函数只是自身调用了自身而已。

一般情况下，尾递归的计算在参数中完成。

我们开始的举例是一个尾递归函数吗？不是，因为那个例子这是调用了自己本省，但是并没有返回，所以还是一个普通的递归函数而已。

使用递归的时候，我们通常在一些技术博客上看到一些关于尾递归优化的东西，这是因为尾递归无论调用多少次函数，都只会占用一份空间，只开辟一个栈帧空间，但是目前 cpython 不支持，然而最常见的解释器就是 cpython 。

Python常见的解释器：cpython、pypy、jpython。

尾递归相比普通递归的优点就是返回值不需要额外过多的运算。

实例

阶乘计算

一个正整数的阶乘是所有小于及等于该数的正整数的积，并且0的阶乘为1。

""" 循环计算 """
def factorial(num):
   if num == 0:
      return 1
   elif num < -1:
      return "只能是零和正整数"
   count = 1
   for i in range(1, num+1):
      count *= i
   return count

res = factorial(5)
print(res)  # 120


""" 使用普通递归 """
def factorial(num):
   if num == 0:
      return 1
   elif num < -1:
      return "只能是零和正整数"
   elif num == 1:
      return num
   return num * factorial(num-1)   # 普通函数返回的是一个表达式

res = factorial(5)
print(res)  # 120


""" 使用尾递归 """
def factorial(num, count=1):
   if num == 0:
      return 1
   elif num < -1:
      return "只能是零和正整数"
   elif num == 1:
      return count
   return factorial(num-1, count*num)   # 尾递归返回的是一个函数，计算式在参数中运算

res = factorial(5)
print(res)  # 120

斐波那契数列

斐波那契数列是以0、1两个数开头，从这个数列从第3个数开始，每一个数都等于前两树之和。

# 使用循环解决
def fibonacci(num):
   x, y = 0, 1

   if num < 1:
      return "输入大于0的数字"
   elif num == 1:
      return 0
   elif num == 2:
      return 1

   for _ in range(num-2):
      x, y = y, y+x
   return y

res = fibonacci(9)
print(res)  # 21


""" 使用普通递归 """
def fibonacci(num):
   if num < 1:
      return "输入大于0的数字"
   elif num == 1:
      return 0
   elif num == 2:
      return 1

   return fibonacci(num-1) + fibonacci(num-2)

res = fibonacci(9)
print(res)  # 21


""" 使用尾递归 """
def fibonacci(num, x=0, y=1):
   if num < 1:
      return "输入大于0的数字"
   elif num == 1:
      return x
   elif num == 2:
      return y

   return fibonacci(num-1, x=y,  y=(x+y))

res = fibonacci(9)
print(res)  # 21