编写递归函数int fib(int n)求Fabonacci数列. Fabonacci数列的定义为： f(n)=f(n-2)+f(n-1) (n>=2) 其中 f(1)=1，f(2)=1。 如输⼊3 (n=3) 则输出： fit(1)=1 fit(2)=1 fit(3)=2

A：

代码如下：

int fib(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
else
{
return fib(n-2) + fib(n-1);
}
}

在这个函数中，我们使用了递归的思想，递归出口为 n=1 或 n=2 时，此时的 f(n) 的值均为 1。而当 n>2 时，f(n) 的值等于 f(n-1) 和 f(n-2) 之和，因此我们可以将问题不断划分为求 f(n-1) 和 f(n-2) 两个子问题，直到问题被划分为 f(1) 和 f(2) 两个基本问题，随后一步步返回结果即可。