递归的概念比较抽象，还是从一个案例入手，逐渐剥开递归的抽象面纱。

递归函数的实现

假如准备要编写一个计算自然数n阶乘的程序。在编写程序之前，需要了解什么是自然数n的阶乘？自然数n的阶乘是所有小于及等于该数的自然数的积。

例如自然数6的阶乘运算是：1 X 2 X 3 X 4 X 5 X 6 = 720。

程序要求给定一个自然数n，计算自然数n的阶乘，并将计算结果输出到控制台。如何用程序来求自然数n的阶乘呢？

观察上面的阶乘案例发现，n的阶乘等于n乘以(n-1)的阶乘。例如：4的阶乘等于4乘以(4-1)的阶乘；5的阶乘等于5乘以(5-1)的阶乘。（n-1）的阶乘又等于（n-1）乘以(n-2)的阶乘。例如：（4-1）的阶乘等于（4-1）乘以（4-2）的阶乘；（5-1）的阶乘等于（5-1）乘以（5-2）的阶乘。

因此求n的阶乘可以写为：

n！= n * (n-1)！
= n * (n-1) * (n-2)!
= n * (n-1) * (n-2) * (n-3)!
…………
= n * (n-1) * (n-2) * (n-3) *(n-4) …… * (n-(n-2)) * 1!

上面的算式对n的阶乘进行层层分解：第一层分解将n的阶乘分解为n与(n-1)阶乘的积；第二层将(n-1)的阶乘分解为(n-1)与(n-2)阶乘的积；第三层将(n-2)的阶乘分解为(n-2)与(n-3)阶乘的积。以此类推，阶乘规模越来越小，最终就是计算1的阶乘。

例如求4的阶乘：

4! = 4 * (4-1)!
= 4 * (4-1) * (4-2)!
= 4 * (4-1) * (4-2) *1!

求4的阶乘采用上面的计算方法，进行三层分解即可。

第一层：4的阶乘分解为4与（4-1）阶乘的积；

第二层：（4-1）阶乘分解为（4-1）与(4-2)阶乘的积；

第三层：(4-2)阶乘分解为(4-2)与(4-3)阶乘的积，也就是(4-2)与1阶乘的积。

经过三层分解，将计算规模为4的阶乘分解为计算规模为1的阶乘，剩余的就是四则运算了。

有了计算阶乘的算法，现在就可以编写程序了。下面给出程序流程图：

在上面的流程图中，把计算n的阶乘封装到factorial(n)函数中，该方法计算传入参数n的阶乘，在方法内部对n的阶乘进行分解，当n=1时直接返回1，因为1的阶乘是1，反之，将n的阶乘分解为n与(n-1)阶乘的积，求（n-1）的阶乘，还是调用factorial(n-1)方法。

从流程图可以看出，在factorial(n)函数内部又调用了factorial(n-1)函数，这种在方法内部又调用自身函数的结构称为递归结构，该方法也称为递归函数。

递归有递推和回归的意思，递推就是把复杂的任务不断分解，让问题规模越来越小，当问题规模小到能够直接解答时，递推就结束了。递推的结束预示着回归的开始，回归从递推结束时问题的解答开始回归，由最简问题的解答按照递推路径反方向获取整个问题的解答。

其实递归蕴含的思想类似我们学过的数学归纳法：为了求解问题p(n)，需要先求解基础问题p(1)，然后再求解p(n-1)，最后获得p(n)的解。

递归结构如下图所示：

递归方法内部分为递归出口和递归体两部分：递归出口是递归的终止条件，一般由条件判断语句和递归终止语句块组成；递归体是包含调用自身方法的语句块。

例如求n的阶乘递归函数可以这么写：

def factorial(n):
  if n == 1:
    return 1
  else:
    return n * factorial(n-1)

求n的阶乘的递归函数名称是factorial，参数是待求阶乘的自然数n。递归出口部分判断n是否为1，如果为1则返回1，因为1的阶乘结果是1。

递归体部分再次调用自身方法对n的阶乘规模进行分解，逐渐降低n的阶乘规模，直至n变为1，满足递归出口的条件。

案例代码：

def factorial(n):
   if n == 1:
    return 1
   else:
    return n * factorial(n-1)
if __name__== "__main__":
   # 计算自然数6的阶乘
   print(factorial(6))
   # 计算自然数20的阶乘
   print(factorial(20))

递归与栈结构

递归是通过栈（stack）这种数据结构来实现的，栈结构是一种特殊的线性表，限定仅在表的一端进行元素的插入和删除。当表中没有元素时，称为空栈。若给定栈：

S = (a1，a2，……，an)

则称a1是栈底元素，an是栈顶元素，表中元素按a1，a2，……，an的次序进栈，出栈的顺序是an，……，a2，a1。也就是说，栈结构的元素访问原则是后进先出，也称为后进先出的线性表，如下图所示。

递归方法每调用一次，Python解释器就会把当前递归函数涉及的参数、局部变量、返回值等数据在栈中压入一个栈帧，一个栈帧保存了函数的参数、局部变量、中间运算结果、返回值等数据。每当递归方法返回时，Python解释器会将当前栈帧弹出并释放掉，并把返回值返回给上层调用者。

用循环替代递归

由于栈空间的内存大小是有限的，当递归调用的次数过多时，会导致栈溢出问题（栈的内存空间不足）。考虑到递归存在栈溢出的问题，在一些情况下，可以使用循环结构来代替递归结构。

下面的案例代码使用循环结构来计算自然数n的阶乘。

案例代码：

def factorial(n):
  fac = 1
  for i in range(1,n + 1):
    fac = fac * i
  return fac
 
if __name__== "__main__":
 
  # 计算自然数6的阶乘
  print(factorial(6))
  # 计算自然数20的阶乘
  print(factorial(20))

上机操作

编写一个程序，递归计算斐波那契数列。

斐波那契数列以递推的方法定义：

F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

案例代码：

def fib_recur(n):
  if n <= 1:
    return n
  return fib_recur(n-1) + fib_recur(n-2)
 
for i in range(1,20):
   print(fib_recur(i),end=' ')