1004[递归]母牛的故事

最近简单复习了一下 python 编码的方法，以此记录一些笔记，本博客仅用于记录算法学习
好久没有刷过算法题，递归算法竟然忘记如何使用了，简单记录一下递归的思想以及递归需要满足的条件。
递归算法：一种直接或者间接调用自身函数或者方法的算法。实质上就是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来求问题的解。

递归满足的条件：

• 一个问题的解可以分解为几个子问题的解；
• 这个问题与分解之后的子问题，除了数据规模不同，求解思路一样；
• 存在基线与终止条件。

优缺点：

• 优点：简单，容易上手
• 缺点：运行效率低，容易出现超时或者超出内存等问题；并且在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储，递归太深，容易发生栈溢出。

下面这个例题，来源于C语言网吧中的习题中的1004，

题目描述：有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

• 输入格式
  输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
  n=0表示输入数据的结束，不做处理。
• 输出格式
  对于每个测试实例，输出在第n年的时候母牛的数量。每个输出占一行。

样例输入：
2
4
5
0
样例输出：
2
4
6

经过分析，我得到了一个关系式：
$$f=\{\begin{array}{ll}n& \text{if }n<=4\\ f(n-1)+f(n-3)& \text{if }n>4\end{array}$$
我编写的递归算法如下所示：

def cow(year):
    if year <= 4:
        return year
    else:
        return cow(year-1) + cow(year-3)

while True:
    n = int(input())
    if n == 0:
        break
    else:
        print(list1[n])
        

提交后，系统显示超出内存。经过查看题解之后，改使用循环了。

list1 = [0, 1, 2, 3]
for i in range(4, 1000):
    list1.append(list1[i-1]+list1[i-3])

while True:
    n = int(input())
    if n == 0:
        break
    else:
        print(list1[n])

这个就没有任何问题了，事实证明，在某些情况下，使用递归容易出现溢出内存或者超时等错误。我们可以对其进行稍稍的修改。