函数递归与二分法

函数递归与二分法

函数递归

1. 递归调用的定义

   递归调用是函数嵌套调用的一种特殊形式，函数在调用时，直接或间接调用了自身，就是递归调用。

     # 直接调用
   def f1():
       print('from f1')
       f1()
   f1()
   # 死循环只是为了举例
   # 间接调用本身
   def f1():
       print('from f1')
       f2()
   ​
   def f2():
       print('from f2')
       f1()
   f1()
   # 调用函数会产生局部的名称空间，占用内存，因为上述这种调用会无需调用本身，python解释器的内存管理机制为了防止其无限制占用内存，对函数的递归调用做了最大的层级限制

2. 递归调用的两个阶段：回溯，递推

   回溯

   是从外向里一层一层的递归调用下去，回溯阶段必须要有一个明确的结束条件，每进入下一次递归时，问题的规模都因该有所减少（否则，单纯地重复调用自身是没有意义的）

   递推

   从里向外一层一层结束递归

3. 总结递归的使用

   1. 必须有一个明确的结束条件

   2. 每次进入更深一层递归时，问题规模相比上次递归都应有所减少

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

       

4. 举例

     def age(n):
    if n == 1:
           return 18
       return age(n-1)+2
   res = age(5)
   print(res)
   # 26

     list_0=[1,[2,[3,[4,[5,[6,[7,[8,[9,]]]]]]]]]
   def func(l):
       for num in l:
           if type(num) is list:
               func(num)
           else:
               print(num,end=' ')
   func(list_0)
   # 1 2 3 4 5 6 7 8 9 

二分法

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

  nums = [1,2,13,15,23,28,33,57,61,76,85,92,100]
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]:
        nums = nums[mid_index+1:]
        binary_search(find_num,nums)
    elif find_num < nums[mid_index]:
        nums = nums[:mid_index]
        binary_search(find_num,nums)
    else:
        print('Find it')
        
binary_search(92,nums)
​
# [1, 2, 13, 15, 23, 28, 33, 57, 61, 76, 85, 92, 100]
# [57, 61, 76, 85, 92, 100]
# [92, 100]
# [92]
# Find it