Python 递归函数

ゝ一纸荒年。 2023-10-08 22:48 32阅读 0赞

### 一、什么是**递归** ###

在函数内部调用自己的函数。

### 二、什么是递归调用 ###

一种特殊的嵌套调用，是指某个函数调用自己或者调用其他函数后再次调用自己。由于不能无限嵌套调用，所以某个递归函数一定存在至少两个分支，一个是退出嵌套，不再直接或者间接调用自己；另外一个则是继续嵌套。  
  
**一般通过函数的输入参数来决定走哪个分支，所以递归函数一般都是带有参数的。**

### 三、应用实例 ###

**1、递归函数：求和**

def  funs(n):
        #1+2+3+4=10
        # 退出递归的分支
        if n==1:
           return 1
        # 递归调用
        return n+funs(n-1)
    
     # 求4的和
    print(funs(4))

#### **2、递归函数：求阶乘** ####

![8cb7ea3287db4bc6a74c92dbbe492710.png][]

def get_factorial(n):  # 定义阶乘函数
        #1*2*3*4=24
        # 退出递归的分支
        if n==1:
            return 1
        # 递归调用
        return n*get_factorial(n-1)
    
     # 求4的阶乘
    print(get_factorial(4))

#### 3、斐波拉契级数 ####

有这样一个数列：1，1，2，3，5，8，13，21，34…。
    其第一元素和第二个元素等于 1，其他元素等于其前面两个元素的和。用数学公式表示如下：

![2d7dc19df76a4c50a225962902e08fd3.png][]

def get_fibo(n):
        # 退出递归的分支
        if n in [1,2]:
            return 1
        # 递归调用
        return get_fibo(n-1)+get_fibo(n -2)
    
    print(get_fibo(1))   # 斐波拉契级数的第1个元素
    print(get_fibo(3))   # 斐波拉契级数的第3个元素
    print(get_fibo(8))   # 斐波拉契级数的第8个元素

#### 4、询问年龄：A比B大8岁，B比C大8岁，C比D大8岁，D是16岁 ####

# 分析：
    # A  age(4) = age(4-1) +8
    # B  age(3) = age(3-1) + 8
    # C  age(2) = age(2-1) + 8
    # D  age(1) = 16
    # 回溯：一层一层的调用下去
    # 递推：满足某种结束条件后，结束递归调用，然后一层一层返回。
    def get_age(n):
        if n==1:  #结束递归调用
            return 16
        else:  #递归调用
            return get_age(n-1)+8
    
    print(get_age(1))  #第1个人年龄
    print(get_age(4))  #第4个人年龄

#### 5、对于一个有n个元素的列表，全排列得到所有的这些排列的列表。 ####

一般对于 n 个元素的列表有 n! 种排列方式。如对于 [1,2,3] 有下面几种排列方法：

def get_combination(ll,start):
        """
        :param ll:  排序的列表
        :param start: 起始位置一般为0
        :return: 空
        """
        end=len(ll)  #记录元素个数
        if start==end:   #递归的结束条件
            print(ll)
        else:
            i=start  #指向本次需要排列的第一个位置（本轮需要固定的位置)
        # 循环排列的序列中的每一个数，
        for n in range(start,end):
            # 依次交换数据
            ll[n],ll[i]=ll[i],ll[n]
            #递归调用
            get_combination(ll,start+1)
            # 回到上一步,交换数据
            ll[n],ll[i]=ll[i],ll[n]
    
    
    #1*2*3=6
    get_combination([1,2,3],0)
    
    #1*2*3*4=24
    get_combination(['red','yellow','green','blue'],0)

**全排列**

![c53cf3055a924150a054e17ec84b18be.png][]

### 四、引用标准库函数：itertools库 ###

![6744ebfb5b83442aa9b5cd125bd06b64.png][]

**1、全排列可以使用这个标准库函数**

import itertools
    print(list(itertools.permutations([1, 2, 3], 3)))
    
    print(list(itertools.permutations(range(3), 2)))

![6eac7f8df7fb40989abe7ec79166325b.png][]

### 五、递归函数调用深度的默认最大值为 1000 ###

1、当调用阶乘使用10万时 ，print(get\_factorial(100000))，发生以下异常：

![24f0e05d05134f4fabda703b02f2a9cf.png][]

> 说明：
> 
>     注意递归的深度。
>     由于递归会产生多次函数调用，而函数调用会消耗代码的栈空间，如果递归的深度太大，会导致栈溢出。
>     以上面的阶乘为例，如果计算 100000 的阶乘，在一般机器上都会出现栈溢出的问题

默认情况下，函数调用深度的最大值为 1000，如果达到或者超过 1000 就会出现上面的错误信息。

import sys
    
    # 得到最大调用深度
    print(sys.getrecursionlimit())

如果希望修改该系统值，也可以通过 sys 模块的接口函数来实现。 如希望最大函数调用深度为 100000，那么可以使用下面的代码进行修改：

# 设定最大调用深度
    sys.setrecursionlimit(10000)

[8cb7ea3287db4bc6a74c92dbbe492710.png]: https://img-blog.csdnimg.cn/8cb7ea3287db4bc6a74c92dbbe492710.png
[2d7dc19df76a4c50a225962902e08fd3.png]: https://img-blog.csdnimg.cn/2d7dc19df76a4c50a225962902e08fd3.png
[c53cf3055a924150a054e17ec84b18be.png]: https://img-blog.csdnimg.cn/c53cf3055a924150a054e17ec84b18be.png
[6744ebfb5b83442aa9b5cd125bd06b64.png]: https://img-blog.csdnimg.cn/6744ebfb5b83442aa9b5cd125bd06b64.png
[6eac7f8df7fb40989abe7ec79166325b.png]: https://img-blog.csdnimg.cn/6eac7f8df7fb40989abe7ec79166325b.png
[24f0e05d05134f4fabda703b02f2a9cf.png]: https://img-blog.csdnimg.cn/24f0e05d05134f4fabda703b02f2a9cf.png