October 15, 2018 · 数据结构与算法 本文字数: 588 阅读时长:2 min 全站字数:344.2k

敏而好学之WHAT——属于盗梦空间的递归

  1. 递归
  2. 实战递归

本文是数据结构与算法之美专栏的学习笔记。

递归

在数据结构与算法中,最难理解的就是知识点之一:递归和动态规划。递归是一种解决问题的方法,先将被求解的问题进行分解后逐个求解,最后再将结果进行合并处理。

递归的通用公式:

f(n)=f(n-1) + c, f(1)=0

能用递归求解的问题首先必须是能够分解为子问题:

  1. 每个子问题之间除了将要处理的数据不同外,处理的思路完全相同。
  2. 每个子问题有一个最终终止条件,从而终结递归,返回结果。

实战递归

对于面试题:假如有n个台阶,每次可以跨1个或者2个台阶,问有多少种走法?

首先这个问题可以分解为:第一步走了1个台阶或者第一步走了2个台阶。那么这个问题就可以分解为:
f(n) = f(n-1) + f(n-2)

递归公式确定后,就需要确定终止条件。如果只有1个台阶,即f(1)=1, 如果有2个台阶。有两种走法:每次走1个或者一次走2个,即f(2) = 2。

可见,使用递归解决问题的方法就是先根据问题的分解策略规律,写出递归公式。然后再确定递归的终止条件。

编写递归代码最容易遇到的问题就是堆栈溢出,这种一般发生在递归过深的情况下。一种优化思路是将重复的子问题的解进行记录,从而去掉一些递归调用,减少递归的深度。一般使用散列表来保存重复的子问题的结果。

递归还有一个问题就是递归会导致过多的函数调用,每次函数调用需要入栈,出栈操作,以及上下文的切换,会影响最终的时间复杂度。

综上,递归代码的特点就是简单,直接;缺点就是空间复杂度高,有堆栈溢出,重复计算,多次函数调用的问题。一般而言,递归代码都可以改写为迭代的方式实现,从而避免递归带来的上述问题。