【Python基础】15. 递归函数 Recursion Fun

什么是递归函数

一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的。

• 递归就是一个函数在它的函数体内调用它自身。

编程语言中的对递归定义:

• 编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。递归函数不能定义为内联函数。

数学中对递归的定义:

• 在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

递归的条件:

• 一个含直接或间接调用本函数语句的函数被称之为递归函数，在上面的例子中能够看出，它必须满足以下两个条件：
  • 1）执行递归函数将反复调用其自身，每调用一次就进入新的一层。
  • 2）必须有结束条件,即必须有一个终止处理或计算的准则。

递归函数的应用

应用一: 计算阶乘(factorial)

• 定义:一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!

• 任何大于等于1 的自然数n 阶乘表示方法：n! = 1*2*3* ...*(n-1)*n,或,n! = n *(n-1)!

• 阶乘的规律:

  1! = 1
  2! = 2 × 1 = 2 × 1!
  3! = 3 × 2 × 1 = 3 × 2!
  4! = 4 × 3 × 2 × 1 = 4 × 3!
  ...
  n! = n × (n-1)!
  

• 用递归函数来计算阶乘: 通过用户输入数字(n)计算阶乘

  # 获取用户输入的数字
  num = int(input("请输入一个数字: "))
  factorial = 1
  
  # 查看数字是负数，0 或 正数
  if num < 0:
      print("抱歉，负数没有阶乘")
  elif num == 0:
      print("0 的阶乘为 1")
  else:
       for i in range(1,num + 1):
          factorial = factorial*I
  
  print("%d 的阶乘为 %d" %(num,factorial))
  

• 上述代码运行结果如下:

  请输入一个数字: 3   #输入3,求3的阶乘. 3! = 3*2*1 =6
  3 的阶乘为 6
  

-上述递归函数的调用过程:

递归函数阶乘3的调用.png

• 在Python中,还可以使用循环来实现阶乘的计算:

  • 使用while循环实现计算3的阶乘

  n=4      #求4的阶乘
  result=1
  I=1
  while i<=4:
    result=result*I
    I+=1
  
  print(result)
  

从上面两中方法的对比可以看出，递归函数的作用和循环的方法效果一样，即递归函数本质上是一个方法的循环调用，注意：有可能会出现死循环。因此，使用递归函数时，一定要定义递归的边界（即什么时候退出循环）。

应用二: 计算斐波那契数列 (Fibonacci sequence)

• 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：
  • 1，1，2，3，5，8，13，21，34，55，89，144……
  • 从3三个数开始,后一个数等于前面两个数的和
  • 在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）

斐波那契数列_兔兔的繁殖.jpg

• 用递归函数来实现获取斐波拉契数列中第n个数字的值:

  #  计算斐波那契数列第n位的值
  def fab(n):
      if n > 2:
          return fab(n-1) + fab(n-2)
      else:
          return 1
  
  #  打印斐波那契数列
  def printfablist(n):
      for i in range(1, n+1):
          print(fab(i),end = ' ')
  
  # 传参调用
  printfablist(int(input('请输入要输出多少项：')))
  

• 上述代码运行结果如下:

  请输入要输出多少项：4    #键入4,求斐波那契数列前四项
  1 1 2 3   # 得到斐波那契数列前四项
  

• 同样的,除了递归函数外,还可以使用while循环来实现斐波那契数列:

  # 获取用户输入数据
  num_n = int(input("请输入你需要几项:"))
  
  # 第一和第二项
  n1 = 1
  n2 = 1
  count = 2
  
  # 判断输入的值是否合法
  if num_n <= 0:
      print("请输入一个正整数。")
  elif num_n == 1:
      print("斐波那契数列：")
      print(n1)
  else:
      print("斐波那契数列：")
      print(n1,",",n2,end=" , ")
      while count < num_n:
          nth = n1 + n2
          print(nth,end=" , ")
          # 更新值
          n1 = n2
          n2 = nth
          count += 1
  

• 上述代码运行结果如下:

  请输入你需要几项:4  #键入4,求斐波那契数列前四项
  斐波那契数列：
  1 , 1 , 2 , 3 ,     # 得到斐波那契数列前四项
  

从上面两中方法的对比可以看出，递归函数的作用和循环的方法效果一样，即递归函数本质上是一个方法的循环调用，注意：有可能会出现死循环。因此，使用递归函数时，一定要定义递归的边界（即什么时候退出循环）。

以上两个案例是递归函数的经典案例，需要记住其使用方法。==循环能干的事,递归都能干;递归能干的循环不一定能干==

递归函数特点

递归：自我调用且有完成状态。

1. 每一级函数调用时都有自己的变量，但是函数代码并不会得到复制，如计算5的阶乘时每递推一次变量都不同；

2. 每次调用都会有一次返回，如计算5的阶乘时每递推一次都返回进行下一次；

3. 递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序；

4. 递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反；

5. 递归函数中必须有终止语句。

递归函数的缺点: 过深的调用会导致栈溢出

递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。

使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

• 使用python写的递归程序如果递归太深, 那么极有可能因为超过系统默认的递归深度限制而出现
  • 例如使用递归计算阶乘时,传入参数值1000来调用函数factoria(1000),运行会报错:

Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
 File "<stdin>", line 4, in factoria
 ...
 File "<stdin>", line 4, in factoria
RuntimeError: maximum recursion depth exceeded

• 解决上述报错问题的方法很简单, 人为将系统设定的递归深度设置为一个较大的值即可:

  import sys
  sys.setrecursionlimit(1000000) #括号中的值为递归深度
  

参考资源:

• 博客园:递归函数的定义和几个小例子
• CSDN:什么是递归函数
• 廖雪峰老师的博客
• 解决python递归栈溢出