Problem

A sequence is an ordered collection of objects (usually numbers), which are allowed to repeat. Sequences can be finite or infinite. Two examples are the finite sequence (π,−2–√,0,π) and the infinite sequence of odd numbers (1,3,5,7,9,…). We use the notation an to represent the n-th term of a sequence.
A recurrence relation is a way of defining the terms of a sequence with respect to the values of previous terms. In the case of Fibonacci's rabbits from the introduction, any given month will contain the rabbits that were alive the previous month, plus any new offspring. A key observation is that the number of offspring in any month is equal to the number of rabbits that were alive two months prior. As a result, if Fn represents the number of rabbit pairs alive after the n-th month, then we obtain the Fibonacci sequence having terms Fn that are defined by the recurrence relation Fn=Fn−1+Fn−2 (with F1=F2=1 to initiate the sequence). Although the sequence bears Fibonacci's name, it was known to Indian mathematicians over two millennia ago.
When finding the n-th term of a sequence defined by a recurrence relation, we can simply use the recurrence relation to generate terms for progressively larger values of n. This problem introduces us to the computational technique of dynamic programming, which successively builds up solutions by using the answers to smaller cases.
Given: Positive integers n≤40 and k≤5.
Return: The total number of rabbit pairs that will be present after n months, if we begin with 1 pair and in each generation, every pair of reproduction-age rabbits produces a litter of k rabbit pairs

兔子繁殖问题

假定如下，

1. 种群在第一个月开始时有一对新生兔子。
2. 一个月后兔子达到生育年龄。
3. 在任何给定的月份，每只育龄兔子都会与另一只育龄兔子交配。
4. 两只兔子交配一个月后，它们会生出一只雄性兔子和一只雌性兔子。
5. 兔子永远不会死亡或停止繁殖

这一生育模式下，每个月的兔子数量(对数)符合斐波那契数列即

1 1 2 3 5 8 ...

问题：
input: 对于给定的月份n，每对兔子生育的兔子对数k
output: 兔子总对数

n = 3, k =5
output: 19

思路：

• 利用递归解决 当兔子生育数为1时F(n) = F(n - 1) + F(n - 2)

  solution -1

  ```python

  每对兔子的后代数量(对数)

  K = 3

def rabbit_fib(n): if n <= 2: return 1 if n == 3: return K + 1 if n == 4: return K2 + 1 else: return rabbit_fib(n - 2) K + rabbit_fib(n - 1)

def main(): print(rabbitfib(n = 5)) if name == ‘_main‘: main()

<a name="zD7Xq"></a>
## solution -2
`Golang`实现
```go
package main
import "fmt"
const K = 3
func fib(n int) int {
    switch {
    case n <= 2:
        return 1
    case n == 3:
        return K + 1
    case n == 4:
        return K*2 + 1
    default: 
        return fib(n - 2)*K + fib(n - 1)
    }
}
func main() {
    res := fib(5)
    fmt.Println(res)
}