算法知识： 三步学会所有递归

「递归」在算法初学者眼中总是一个令人头疼的问题

但其实，这种可以将一个问题拆解为多个重复子问题的算法只要我们掌握了其中的 “套路” ，便可以游刃有余的解决所有递归类问题。下面我们就开始吧～

一、青蛙跳台阶

我们首先以最简单的「青蛙跳」为例子来拆解递归问题

剑指 Offer 10－ II． 青蛙跳台阶问题【超级简单】

问题定义：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

第一步：明确递归关系

当我们确定了一个问题是可以使用递归思想解决的时候，我们一定可以明确其中的递归关系，即该问题的子问题之间存在的函数关系。在本题中，我们要 求解青蛙跳上一个 n 级的台阶总共有多少种跳法；我们知道青蛙一次只可以跳1级或2级的台阶，那么在小蛙跳上第n 级台阶的前一步时，小蛙?一定站在第n－1 级或第n－2 级台阶上。所以如果设「青蛙跳上一个 n 级的台阶」共有 f（n） 种跳法；则我们可以得到其中的函数关系为f（n） ＝ f（n－1） ＋ f（n－2）则可以得到函数

def f（n）：    return f（n－1） ＋ f（n－2）

第二步：明确递归退出条件

做为一个递归函数，其最容易犯的错误就是一猛子扎进死循环中再也出不来；

为了避免这种情况的发生，设定一个严谨的递归结束条件是十分必要的。

在本题中我们得到「一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶」；

可以知道，当台阶数 n 为 1 时，此时不需要进行求解，可以直接知道小蛙?只有一种跳法，一次就可以跳上去。

当台阶数 n 为 2 时，小蛙?可以 一次跳两个台阶 或 一次跳一个台阶一共跳两次，可以有两种跳法。

则我们可以得到函数停止条件

def f（n）：  if n ＝＝ 1：    return if n ＝＝ 2：    return 2  return f（n－1） ＋ f（n－2）

第三步：校验整体逻辑

在上述函数中显然，对于 n ，我们只考虑到了n ＞＝ 1的情况；

为了题目更严谨（不仅本题，所有题目都要记得最后校验），我们最后补全可能存在的所有情况；

即根据算法题命题，最后必须要考虑到的边界条件。

又因为题目示例中给到：

所以得到最后的函数：

def f（n）：  if n ＝＝ 0：    return if n ＝＝ 1：    return return f（n－1） ＋ f（n－2）

（当然，该题最好的解法是使用动态规划方法～ 但我们本篇文章着重在于递归思想的拆解，因此暂时不讲这种解法）

想必，前面的内容过于简单

大家都已经跃跃欲试了吧

接下来，我们使用树?的问题来验证这三步方法