目录
1.递归含义
2.递归技巧之递归辅助函数
3.递归技巧之尾递归与辅助参数
4.递归技巧之历史数据全部保存
5.实例研究
例子1：大厂python面试题
例子2：递归深度遍历文件夹
1.递归含义
递归函数就是一个调用自己的函数。
递归分为直接递归和间接递归，直接递归就是 A 调用 A，间接递归就 A 调用 B，B 调用 A。
有的问题不好用迭代解决，这个时候可以考虑用递归。
注意事项
- 注意递归占用内存大，可能引起栈溢出错误
- 注意设置终止条件
例子1：计算阶乘
def factorial(n):if n == 1:return 1else:return n * factorial(n - 1)print(factorial(5)) # 120例子2：计算斐波那契数
def fib(index):if index == 0:return 0elif index == 1:return 1else:return fib(index - 1) + fib(index - 2)print(fib(4)) # 3例子3：计算递归调用次数
用列表或者 global 函数
def fib(index):sum_list.append(1)global countcount += 1if index == 0:return 0elif index == 1:return 1else:return fib(index - 1) + fib(index - 2)sum_list = []
count = 0
print(fib(10))
print(sum(sum_list)) # 177
print(count) # 177 例子4：注意调用顺序的差异
def g(n):if n > 0:print(n, end=" ")g(n - 1)def f(n):if n > 0:f(n - 1)print(n, end=" ")g(7) # 7 6 5 4 3 2 1print()f(7) # 1 2 3 4 5 6 7 例子5：判断一个整数是否为回文数
def is_left_equal_right(s):if len(s) <= 1:print(True)return Trueelif s[0] != s[-1]:print(False)return Falseelse:is_left_equal_right(s[1:-1])is_left_equal_right("12321") # True
is_left_equal_right("a232a") # True
is_left_equal_right("12325") # False2.递归技巧之递归辅助函数
在递归程序设计中定义第二个函数来接收附加参数，这个函数被称为递归辅助函数 。
这个辅助函数在设计关于字符串和数组问题的递归解决方案上是非常有效的。
前面递归的is_left_equal_right 函数每次都要使用切片，它会创建一个字符串，这不够高效
为避免创建新的字符串，可以使用 low 和 high 下标来表明子串的范围。
# 启动函数
def is_left_equal_right(s):is_left_equal_right_helper(s, 0, len(s)-1)# 递归辅助函数
def is_left_equal_right_helper(s, low, high):if high <= low:print(True)return Trueelif s[low] != s[high]:print(False)return Falseelse:is_left_equal_right_helper(s, low+1, high-1)is_left_equal_right("12321") # True
is_left_equal_right("a232a") # True
is_left_equal_right("12325") # False例子2：使用递归进行选择排序
import randomdef sort1(one_list):sortHelper(one_list, 0, len(one_list) - 1)def sortHelper(one_list, start, end):# 设置终止条件if start < end:# 找到最小值minIndex = startminValue = one_list[minIndex]for i in range(start, end + 1):if one_list[i] < minValue:minIndex = iminValue = one_list[minIndex]# 与开始位置的值交换if minIndex != start:one_list[minIndex] = one_list[start]one_list[start] = minValue# one_list[start], one_list[minIndex] = one_list[minIndex], one_list[start]# 继续递归sortHelper(one_list, start + 1, end)def main():list1 = [x for x in range(10)]print(list1)random.shuffle(list1)print(list1)sort1(list1)print(list1)main() 例子3：使用递归进行二分查找
def binarySearch(lst, key):low = 0high = len(lst) - 1return binarySearchHelper(lst, key, low, high)def binarySearchHelper(lst, key, low, high):if low > high: # 列表中不存在这个值时，返回一个负数return -(low + 1) # key 比 lst[low]大，比 lst[low + 1]小，如果将 key 插入列表，它将在 low + 1 位置mid = (low + high) // 2if key < lst[mid]:high = mid - 1return binarySearchHelper(lst, key, low, high )elif key == lst[mid]:return midelse:low = mid + 1return binarySearchHelper(lst, key, low, high)def main():lst = [x for x in range(11, 21)]print(lst) # [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]print(binarySearch(lst, 15)) # 4print(binarySearch(lst, 19)) # 8print(binarySearch(lst, 16.1)) # -7main()3.递归技巧之尾递归与辅助参数
如果从递归调用返回时没有待处理操作要完成，那么这个递归函数就被称为尾递归
结尾调用自己的递归函数不一定是尾递归，比如前面的计算阶乘 factorial 递归函数，因为对于fib(index - 1) + fib(index - 2)来说，fib(index - 1) 调用时，还有未完成的 fib(index - 2)
尾递归是很有必要的，因为最后一个递归调用结束时，函数调用也就结束了，因此无须将中间调用存储在栈中。
通常可以使用辅助参数将非尾递归函数转为递归函数。使用这些参数来放置结果。
例子1： 将阶乘函数改为尾递归函数
# 启动函数
def f(n):return f2(n, 1)# 递归辅助函数
def f2(n, result):if n == 0:return resultelse:return f2(n - 1, n * result)print(f(5)) # 120 例子2：将斐波那契数改为尾递归函数
def fib(index, start_value=0, next_value=1):if index == 0:return start_valueelif index == 1:return next_valueelse:# s_value = next_value# n_value = start_value + next_value# return fib(index-1, s_value, n_value)return fib(index - 1, next_value, start_value + next_value) print(fib(2)) # 1
print(fib(4)) # 3
print(fib(6)) # 84.递归技巧之历史数据全部保存
对于那些可能会重复计算的数据，我们可以将它们保留保存下来，避免每次都要计算一次，提高程序的效率
斐波那契数列
改进前
def fib(index):if index == 0:return 0elif index == 1:return 1else:return fib(index - 1) + fib(index - 2) 改进后
already_know = {0: 0, 1: 1}def fib_by_dict(n):if n not in already_know:new_value = fib_by_dict(n-1) + fib_by_dict(n-2)already_know[n] = new_valuereturn already_know[n]for i in range(50):print(fib_by_dict(i), end=' ')print()
print(already_know)5.实例研究
例子1：大厂python面试题
问题
25 个台阶一次走 1 个或者 2 个有多少种走法解决思路：
- 对于1个台阶，1, 1种走法
- 对于2个台阶，11, 2, 2种走法
- 对于3个台阶，111, 12, 21, 3种走法
- 对于4个台阶，1111, 112, 121, 211, 22, 5种走法
可以观察到对于有n个台阶时，第一次的选择要么1个，要么2个。当第一次选择1个时，则对剩下n-1个台阶的走法进行判断，假设有f(n-1)个；当第一次选择2个时，则对剩下n-2个台阶的走法进行判断，假设有f(n-2)个。
因此可以看到有n个台阶时，f(n) = f(n-1) + f(n-2)，显然这就是递归，其中终止条件f(1)=1，f(2)=2
因此答案
def f(n):if n == 1:return 1elif n == 2:return 2else:return f(n-1) + f(n-2)print(f(25))例子2：递归深度遍历文件夹
import osdef getall(path, treeshow):filelist = os.listdir(path)for filename in filelist:filepath = os.path.join(path, filename)if os.path.isdir(filepath):print(treeshow, "文件夹", filename)newspace = treeshow + "\t"getall(filepath, newspace)else:print(treeshow, "文件", filename)getall(r"D:\test", "")效果
文件 1.txt文件 2.txt文件夹 temp文件夹 company文件夹 .git文件 config文件 description文件 HEAD文件夹 hooks文件 applypatch-msg.sample文件 commit-msg.sample文件 fsmonitor-watchman.sample文件 post-update.sample文件 pre-applypatch.sample文件 pre-commit.sample文件 pre-merge-commit.sample文件 pre-push.sample文件 pre-rebase.sample文件 pre-receive.sample文件 prepare-commit-msg.sample文件 push-to-checkout.sample文件 update.sample文件 index文件夹 info文件 exclude文件夹 logs文件 HEAD文件夹 refs文件夹 heads文件 master文件夹 remotes文件夹 origin文件 HEAD文件夹 objects文件夹 info文件夹 pack文件 pack-ebca6bbea49bad313f9e360e6c1a54271a77f478.idx文件 pack-ebca6bbea49bad313f9e360e6c1a54271a77f478.pack文件 packed-refs文件夹 refs文件夹 heads文件 master文件夹 remotes文件夹 origin文件 HEAD文件夹 tags文件 README.md文件 test.txt文件 yyyy.txtend
