如何理解和解决递归问题
- 关于如何判断一个问题是否可以用递归解决
- 写递归的思路是什么?
- 想清楚我们的函数要解决的问题是什么
- 找到递归结束的条件,常用的方法是考虑参数很小的情况,小到可以直接得出想要的结论,这时可以把这个作为结束条件,但是需要注意条件泄漏
- 找到等价关系式,迭代表达式(核心)
- 写完等价关系式后,要返回去检查会不会出现无限递归的情况,递归条件是否严谨,同时也需要考虑特殊测试用例
- 例子:
- 求阶乘
我们要求阶乘
n=1时ans=1,n=2时ans=2
等价关系式
f(n) = n*f(n-1)
每次递归使
n-1
,因此递归结束条件可以从1或2开始向下兼容
- 求斐波那契数列第n项
- 小青蛙跳台阶
- 我们要求总的跳法数目
- n=1时ans=1,n=2时ans=2,n=3时ans=3
- 直接找出等价关系式有点困难,需要把问题拆解到每一个选择:每一次决定都有两个选项:跳一级或跳两级。跳一级使得剩余台阶
n-1
,这种选择使得我们后续共有f(n-1)
种跳法;跳两级使得剩余台阶数n-2
,这种选择使得我们后续共有f(n-2)
种跳法,那么我本次做选择之前就共有f(n-2)+f(n-1)
种跳法,即f(n)=f(n-1)+f(n-2)
种跳法,这也就是递归表达式- 由于n每次递减1和2,因此我们得结束条件需要从
n=2
开始向下兼容,如果输入允许为0,那么还要一并考虑n=0
的情况
- 反转单链表
假设函数
reverseList(head)
的功能时反转单链表,其中head表示链表头节点。结束条件:链表为空,或者只有一个节点
等价关系:把链表头单独拆下来,将整个链表看成一个节点(链表头)和剩余链表,那么反转整个链表就是把剩余链表反转,并且把表头插到尾部,自身指向
null
。而反转的剩余链表,尾部为反转前的头部,因此只要再反转前保存tmp = head->next
,反转后tmp->next = head
,再
head->next = null
,反转就完成了。
- 递归的优化
- 考虑是否重复计算