序列是一组有序对象的集合，它有如下特征：

  1. 序列内元素可以重复；
  2. 序列可以是有限的，也可以是无限的。

递推关系是一种用来定义序列的方法，可以通过前面的项，推导出后面的项。如斐波那契兔子问题，某月的兔子数，等于上一个月的兔子数，加上新生的兔子数；一个关键的现象是，因为新生的兔子要隔一代才有繁殖能力，所以某月新生的兔子数等于两个月前的兔子数。因此某月的兔子数可以通过下面的公式描述：

Fn = Fn-1 + Fn-2（F1=F2=1）

这便是递推。由递推启发的动态规划思想，是生物信息学中许多比对软件的算法基础。

给定： 正整数n和k。

**需得：**经过n个月后总共有多少对兔子。假定从一对兔子开始，每一代每对成年兔子生k对小兔子（不是一对）。

示例数据

1

5 3

示例结果

1

19

Python实现

Rabbits_and_Recurrence_Relations.py

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import sys

def fib(n, k):
    f = [1] * n
    for i in range(2, n):
        f[i] = f[i-1] + f[i-2] * k
    return f[n-1]

def fib2(n, k):
    return 1 if n < 3 else fib(n-1, k) + fib(n-2, k)*k

def test():
    return fib(5, 3) == 19 and fib2(5, 3) == 19

if __name__ == '__main__':
    if not test():
        print("fib: Failed")
        sys.exit(1)
    print(fib(35, 3))

解本题的关键是要理解：

  1. 本月的兔子数 = 上月的兔子数 + 新生的兔子数
  2. 由于兔子要隔一代才能繁殖，因此上月的新生兔子，在本月不繁殖，有繁殖能力的是上上月的兔子，并且要乘以繁殖系数k。

本题用了两种方式解决，递推与递归，两者的区别是：

  1. 递推：从已知到未知，从小到大；就本题来说，就是以第1，2个月为基础，逐步推导出后续每一个月的兔子数。
  2. 递归：从未知到已知，从大到小。就本题来说，要计算某月的兔子数，先计算前面两个月的兔子数，如此循环，直到把任务都分解成计算第1，2个月的兔子数，而这两个月的兔子数是已知的。

学生信欢迎关注我的知乎，请“点赞”为爱发电，只“收藏”不点赞都是耍流氓。