Python-函数递归

一、函数递归

引入

函数的递归调用：就是在调用一个函数的过程中又直接或间接地调用自己
示例1：直接调用自己

def foo():
    print('hello')
    foo()

foo()  # 无限递归，会抛出异常，调用python对象超过最大递归深度

示例2：间接调用自己

def bar():
    print('from bar')
    foo()

def foo():
    print('hello')
    bar()

foo()  # 也会抛出异常

为何无限递归吧会抛出异常？？？
因为无限的递归会导致内存溢出，所以python设定了最大的递归层数，我们应该给递归设置结束条件，然后返回

import sys
print(sys.getrecursionlimit())  # 可查看当前最大递归层数
print(sys.setrecursionlimit(2000))  # 可设置新的最高递归层数

递归调用

应该分为两个阶段
①、回溯（挖井） ：一层一层地递归调用下去
②、递推（从井里往外跳）：在满足某一条件的情况下结束回溯，然后开始向上一层层返回
小案例：计算年龄，小一说比小二多大十岁，小二比小三大十岁，小三比小四大十岁，小四比小五大十岁。

salary(5) = salary(4) + 10
salary(4) = salary(3) + 10
salary(3) = salary(2) + 10
salary(2) = salary(1) + 10
salary(1) = 18

'''递归书写思路'''
n=1   salary(n) = 18
n!=1  salary(n) = salary(n-1) + 10
'''递归使用：'''
def salary(n):
    if n == 1:
        return 18
    return salary(n-1) + 10

res=salary(5)
print(res)

二分法使用场景

关于算法的相关了解与学习笔记可查看本博客另一专题《算法》

'''
从小到大排列的一个数字列表,找某个数是否在其中，此处采用算法的方式，不使用python自带的in方法
'''
nums = [11, 13, 32, 47, 53, 73, 84, 91,101,111,222,333,444,5555]

def binary_search(l,find_num):
    print(l)
    if len(l) == 0:
        print('find_num not exists')
        return
    mid_index = len(l) // 2
    if find_num > l[mid_index]:
        right_l=l[mid_index+1:]
        binary_search(right_l,find_num)
    elif find_num < l[mid_index]:
        left_l=l[:mid_index]
        binary_search(left_l,find_num)
    else:
        print('find it')

binary_search(nums,85)

递归的应用场景

当你不知道该重复做多少次，但是知道在什么情况下该结束的时候，用递归会很好。