递归

• 递归: 函数直接或间接调用自身,是一种常用的编程技巧
• 如果递归没有终止条件,将会一直消耗栈空间,最终导致栈内存溢出。所以,递归必须要有一个明确的结束递归的条件,也叫作边界调节、递归基。
• 使用递归不是为了求得最优解,是为了简化解决问题的思路,代码会更简洁,递归求出来的很有可能不是最优解,也有可能是最优解

递归思想

• 拆解问题

• 把规模大的问题变成规较小的同类型问题
• 规模较小的问题又不断变成规模更小的问题
• 规模小到一定程度可以直接得出它的解

• 求解

• 由最小规模问题的解得出较大规模问题的解
• 由较大规模问题的解不断得出规模更大问题的解
• 最后得出原来问题的解

• 凡是可以利用上述思想解决问题的,可以尝试使用递归

• 很多链表、二叉树相关的问题都可以使用递归来解决。因为链表、二叉树本身就是递归的结构(链表中包含链表、二叉树中包含二叉树)

递归使用套路

• 1、明确函数的功能。先不要去思考里面代码怎么写,首先搞清楚这个函数是干嘛用的,能完成什么功能。
• 2、明确原问题与子问题的关系。寻找 f(n)与 f(n-1)的关系
• 3、明确递归基(边界条件)。递归的过程中,子问题的规模在不断减小,当小到一定程度时可以直接得出它的解。寻找递归基,相当于是思考:问题规模小到什么程度可以直接得出解?

递归的复杂度

• 时间复杂度: 与递推式有关系
• 空间复杂度: = 递归深度* 每次调用所需的辅助空间