递归算法10——复杂递归之大牛生小牛问题

 

一只刚出生的小牛，4年后生一只小牛，以后每年生一只，现有一只刚出生的小牛，问20年后共有多少只。

【分析】

问题可以分成两种情况处理：小于4年时，只有一只小牛；大于4年时，小牛长成大牛，开始生小牛。递归函数可以这样描述：

如果year<4，则返回1表示只有一头牛；当year≥4时，第4年的大牛开始生小牛，每年生一个。而且每隔3年，小牛长成大牛，开始生小牛。

code：
 

#include<stdio.h>
#include <iostream>
long Cow(int year);
void main()
{
	long n;
	int year;
	printf("请输入年数:");
	scanf("%d", &year);
	n = Cow(year);
	printf("%d年后牛的总数:%d\n", year, n);
	system("pause");
}
long Cow(int years)
{
	long count = 1;
	int i, subYears;
	if (years <= 3)
	{
		return 1;
	}
	i = 4;
	while (i <= years)
	{
		subYears = i - 3;
		count += Cow(subYears);
		i++;
	}
	return count;
}

结果：