递归

2020-06-27 本文已影响0人 isLJli

递归的概念分析

递归又分为"递"和“归”，它的大致思路是把方法传递到最低下的最小已知方法，然后在从最小方法一步一步往上求答案归回来。举个例子，假如你去电影院看电影，因为环境太黑你不知道座位在哪一排，你就去问你前一排的人它的座位在第几排，只要知道前一排的座位是第几排就可以知道当前的座位是第几排，而如果前一排的人也不知道他的座位是第几排就会往前问他的前一排，直到问到第一排才给出答案是第一排，这就是递。然后在根据第一排的答案一排一排的往上算，直到算到第n排，这就是归。

image

电影院座位递归

写递归的思路

递归就是将一个问题分解成子问题，直到最后一个子问题有了答案，在往上求解父问题。

首先，不要视图用人脑去逐步分析整个流程，因为有些问题是有几个子问题的解法的，这时用人脑就很难去分析。我们要假设下一个子问题已经知道答案了。

递归的最重要两个问题:第一个父问题跟下面子问题的关系，子问题的终止条件。

例子:假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？

思路：我们把N个台阶作为父问题，那它的下一个子问题可能是第n-1个台阶的总解法，也有可能是第n-2个台阶的总解法。现在我们把第n-1和n-2台阶的总解法当作已知，那么对应公式为f(n)=f(n-1)+f(n-2)。我们现在来算子问题的终止条件：有可能是只剩一个台阶，那么f(1)=1,有可能只剩两个台阶，那么f(2)=2。