函数递归

函数递归

什么是函数递归

函数的递归是函数嵌套调用的一种特殊形式，

特殊在调用一个函数的过程中又直接或者间接地调用该函数本书

递归本质就是一个循环的过程，

但是递归必须满足两个原则：

1. 每进入下一层递归，问题的规模必须有所减少

2. 递归必须有一个明确的结束条件或者说有一个明确的进入下一层递归的条件

 

并且递归有两个明确的阶段

回溯：一层一层地递归调用下去

递推：在某一层结束掉递归，然后一层一层返回

为何要用递归

在某些情况下，基于递归来使用重复的过程比while循环更加简单

如何用递归

def age(n):
    if n == 1:
        return 18
    return age(n-1)+2

res=age(5)
print(res)

list1=[1,[2,[3,[4,[5,[6,[7,[8,[9,]]]]]]]]]
def func(l):
    for item in l:
        if type(item) is list:
            # 将item当作一个新列表传给功能本身
            func(item)
        else:
            print(item)
func(list1)

二分法

二分法是算法的一种，算法是如何高效地解决问题的思路

nums = [1, 13, 15, 23, 27, 31, 33, 57, 73, 81, 93, 94, 97, 101]  # 从小到大排列的数字列表
def binary_search(find_num,nums):
    print(nums)
    if len(nums) == 0:
        print('not exists')
        return

    # 功能
    mid_index = len(nums) // 2
    if find_num > nums[mid_index]:
        # in the right
        nums=nums[mid_index+1:]
        # 重新运行功能,传入新列表
        binary_search(find_num,nums)
    elif find_num < nums[mid_index]:
        # in the left
        nums=nums[:mid_index]
        # 重新运行功能,传入新列表
        binary_search(find_num,nums)
    else:
        print('find it')


# binary_search(97,nums)
binary_search(94,nums)