递归求斐波那契数列

什么是斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……

这个数列从第 3 项开始，每一项都等于前两项之和。

思路

因为斐波那契数列的每一项都等于前两项之和，因此，我们可以使用公式表达为：

F(N) = F(N-1) + F(N -2)

因为，我们就可以定义一个求斐波那契数列第 N 项值的函数 Fibonacci，那么 Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)，这个就可以使用递归来实现。

同时，我们可以设置递归的出口就是 N 等于 1 或者 N 等于 2 时，值都为 1。具体推导过程可以简化如下：

F(1) = 1
F(2) = 1
F(3) = 1 + 1 = F(1) + F(2) = 2
F(4) = 2 + 1 = F(3) + F(2) = 3
F(5) = 3 + 2 = F(4) + F(3) = 5
F(6) = 5 + 3 = F(5) + F(4) = 8
...
F(N) = F(N-1) + F(N-2)

实现

#include <stdio.h>
int fibonacci(int n)
{
	if (n == 1 || n == 2)
	{
		return 1;
	}
	else
	{
		return fibonacci(n-1)+fibonacci(n-2);
	}
}
int main()
{
	printf("嗨客网（www.haicoder.net）\n\n");
	int f5 = fibonacci(5);
    int f6 = fibonacci(6);
	printf("fibonacci5 = %d, fibonacci6 = %d\n", f5, f6);
	return 0;
}

运行结果如下：

我们使用了递归的方式求斐波那契数列的第 N 项的值，递归的条件就是第 N 项的值等于第 N-1 项的值与第 N-2 项的值的和，递归的出口就是 n 等于 1 或者 n 等于 2 时，直接返回 1。