递归函数
认识递归
递归指的是函数调用自己。编写递归函数,必须告诉它何时停止,每个递归函数包含两个部分:
- 基线条件
base case
- 递归条件
recursive case
递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环
1 | def look_key(box): |
调用栈 call stack
调用栈可能很长,将占用大量的内存。栈的两个操作:
- 压入元素(插入)
- 弹出元素(删除并读取)
1 | def greet(name): |
求阶乘
1 | def factorial(n): |
求斐波那契数列
1,1,2,3,5,8,13,…最开始的两个值1和1,后面的数是前面两个数的和
1 | def fibonacci(n): |
分而治之
分而治之的工作原理
- 找出最简单的基线条件:基线条件很可能是空数组或只包含一个元素的数组
- 确定如何缩小问题的规模,使其符合基线条件
1 | # 列表求和:for遍历循环 |
二分法查找的分而治之思想
1 | def binary_search_impl(alist, item): |
快速排序
快排实现
快速排序采用的是分而治之(divide and conquer,D&C)的策略。找到一个基准值,再找出比它大和比它小的值:
整个数组分成:
- 一个由所有小于基准值的数字组成的子数组;无序
- 基准值
- 一个由所有大于基准值的数字组成的子数组;无序
对这两个子数组进行快速排序
1 | # 递归:快排 |
快排的平均运行时间$O(n logn)$,归并排序的运行时间总是$O(n logn)$
快排运行时间
最糟情况:$O(n)*O(n)$
最佳情况:$O(nlogn)$
最佳情况就是平均情况