兔子递归想到的一些道理

兔子递归问题

前几天有个同事考我一个有关兔子递归的题目:题目如下

有一对兔子,生长到第3个月时。开始生第一对兔子,并且以后每月生一对兔子,小兔子生长三个月后,也开始生兔子,问N个月后兔子的总数量.
刚开始我一想,这不就是大一就做过的吗,这个就是经典的斐波拉契啊。于是在草稿纸上画着

1
2
月份 1 2 3 4 5 6 7
对数 1 1 2 3 5 8 13

哦,然后觉得,可以使用递推法。也可以使用递归法。不过看我那同事,估计是说要用递归了。 然后就用递归写程序了。
其实都知道
不就是f(n)=f(n-1)+f(n-2) 吗(n>2时), 边界就是f1=1, f2=1

但是我并没有写,这貌似和我所理解的递归思维不一样。我所理解的,不是说通过规律找到

1
f(n)=f(n-1)+f(n-2)。

大家都知道,递归就是自己调用自己,但是一个抽象的方法,如何自己调用自己呢。我所理解的是将一种重复问题,分别为同类子问题的方法,这个子问题也是一种重复问题。而我们应该是要有这种思想。

分析

回到这个问题, f(n)=f(n-1)+f(n-2),如果从一般的情况来说,这三个函数分别代表什么意思呢。

  • f(n)代表第n月时兔子总数
  • f(n-1)代表第n-1个月时的兔子总数
  • f(n-2)代表第n-2个月时的兔子总数.

可这个公式到底是怎么来的呢。
后来想了想,才想清楚
这里先给这个题目说清晰一点,第三个月开始生兔子,要说明是第三个月初。然后问第n个月后有多少只兔子,其实问的是第n个月底
题目清晰后,分析如下

1
2
第n个月的兔子总数 = 第n-1个月的兔子总数+第n月初新生的兔子总数
而第n月初新生的兔子总数,其实就是第n-2个月时的兔子的总数,这是因为n-2个月时的兔子总数,在第n月初都将会生兔子。

所以得出

1
第n个月的兔子总数 = 第n-1个月的兔子总数 + 第n-2个月时的兔子的总数.

也就是

1
f(n)=f(n-1)+f(n-2).

这里我们可以看出,我们并不是想要通过找规律得到这个递归的过程,而是应该根据一种划分子问题的思维,去寻找这个规律。
如果有这种思维,这道题可以将这个生长到第3个月改为第k个月
还是一样的分析方法

1
2
第n个月的兔子总数 = 第n-1个月的兔子总数+第n月初新生的兔子总数
第n月初新生的兔子总数 = 第n-k+1时兔子的总数.因为第n-k+1时的兔子总数,在第n个月时,肯定都会生兔子。

所以

1
f(n)=f(n-1)+f(n-k+1)。

补充几个类似思想的问题

然后再补充几个可以用划分子问题的方式,这是一种递归问题

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

  2. 矩形覆盖问题
    我们可以用21的小矩形横着或者竖着去覆盖更大的矩形, 请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

  3. 二叉树的前序遍历,中序遍历,后续遍历等问题

其实这几种问题,都不是说找规律来的,都是划分为同类子问题的方式

要有自己的思考

所以,网上的挺多内容,都需要有自己的思考,多想想为什么,有时候即使自己想错了也可以,但毕竟还是自己思考过,而不是一味的参考网上的方法。
其实从小到大,我思考都不会直接看答案,天生就对答案有一种怀疑的态度。之前刷数学题, 物理题,基本都是自己去做,如果和答案不一样,我一般都是先怀疑答案有问题,然后一个一个对比,如果是自己的问题,那OK。自己也会对比为什么要这样做,正是由于有这种思维,如果一个你理解了的问题,无论这个问题再怎么变化,你也是会做的。做算法也是一样,如果去刷leetcode,或者编程中,一有问题就百度google,然后网上说什么,就认同什么,其实这对自己提升是非常小的,甚至,大多时候先看完答案,总有一种先入为主的思维,让你不得不往答案的这个思路去想,但是有时候这并不是最好的,也有时也没有涉及到问题的本质,只有多思考,多怀疑,这样,才能对事物理解的更加深刻。(不过这样就只有一个不好的,也是大多理工科的一个通病,容易钻牛角尖,其实怀疑也需要合理,该相信的还是要相信,只不过更多要有自己的想法,并且尽量去客观,辩证的看待)
最后再补充一句,看新闻别看腾讯今日头条百度等新闻,更不要看在腾讯百度今日头条等看大家的评论。