函数递归与二分法

函数递归

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