【头歌实训：递归实现斐波那契数列】

头歌实训：递归实现斐波那契数列

任务描述

本关任务：递归求解斐波那契数列。

相关知识

为了完成本关任务，你需要掌握：1.什么是递归，2.如何编写递归算法。

递归相关知识

在数学与计算机科学中,递归(recursion)是指在函数的定义中又调用函数自身的方法。若p函数定义中调用p函数,称之为直接递归;若p函数定义中调用q函数,而q函数定义中又调用p函数,称之为间接递归。任何间接递归都可以等价地转化为直接递归。
如果一个递归过程或递归函数中的递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。

递归举例

下面是递归求n（正整数）的阶乘的递归算法。

int fun(int n){
if(n == 1) //语句1
return 1; //语句2
else //语句3
return n * fun(n - 1);//语句4
}
在函数fun(n)的求解过程中直接调用fun(n-1)(语句4),所以它是一个直接递归函数;又由于递归调用是最后一条语句,所以它又属于尾递归。
递归算法通常把一个大的复杂问题层层转化为一个或多个与原问题相似的规模较小的问题来求解,递归策略只需少量的代码就可以描述出解题过程所需要的多次重复计算,大大减少了算法的代码量。
一般来说，能够用递归解决的问题应该满足以下3个条件:

需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同,只是在数量规模上不同。
递归调用的次数必须是有限的。
必须有结束递归的条件来终止递归。

何时使用递归

在以下3种情况下经常要用到递归的方法。

定义是递归的

有许多数学公式、数列和概念的定义是递归的，例如求n!和斐波那契( Fibonacci)数列等。对于这些问题的求解过程,可以将其递归定义直接转化为对应的递归算法，例如求n!可以转化为上面的递归算法。

数据结构是递归的

算法是用于数据处理的，有些存储数据的数据结构是递归的，对于递归数据结构，采用递归的方法设计算法既方便又有效。
例如，单链表就是一种递归数据结构，其结点类型声明如下:

/* 单链表结点类型定义 */
typedef struct Node
{
int data;
struct Node *next;
} LinkNode;
其中,结构体Node的声明中用到了它自身，即指针域next是一种指向自身类型的指针。图1所示为一个不带头结点的单链表L的一般结构,L标识整个单链表,而L->next标识除了结点L以外其他结点构成的单链表，两种结构是相同的,所以它是一种递归
数据结构。

图1 不带头结点单链表L示意图

对于这样的递归数据结构,采用递归方法求解问题十分方便。例如,求一个不带头结点的单链表L的所有data域(假设为int型)之和的递归算法如下:

int Sum(LinkNode *L)
{
if (L == NULL)
return 0;
else
return (L->data + Sum(L->next));
}

问题的求解方法是递归的

有些问题的解法是递归的,典型的如梵塔问题的求解。

编程要求

本题要求实现一个递归函数int fib(int n)，返回斐波那契数列的第n项。例如如果n=5，则该函数应该返回5。

注：该数列的前面几项是: 1 1 2 3 5 8 13 21 34 …

根据提示，在右侧编辑器补充代码，计算并输出斐波那契数列第n项的值。

测试说明

平台会对你编写的代码进行测试：

测试输入：5
预期输出：5

测试输入：1
预期输出：1

提示：

1 <= n <= 46

开始你的任务吧，祝你成功！

源代码：

 
#include <stdio.h>/*** @Param(n):1<=n<=46* 功能：返回斐波那契数列的第n项*/
int fib(int n)
{/******************** begin ********************//*if(n == 1 || n == 2) return (1);  //斐波那契数列第一二项为1return (fib(n - 1) + fib(n - 2));  //当从第三项开始为前两项的和*/if(n==1 ||n==2)return 1;else if(n==3) return 2;else if(n==4) return 3;else if(n==5) return 5;else if(n==6) return 8;else if(n==7) return 13;else if(n==8) return 21;else if(n==9) return 34;else if(n==10) return 55;else if(n==11) return 89;else if (n<=46) return fib(n-1)+fib(n-2);/******************** end **********************/  
}int main(int argc, char const *argv[])
{int n;while (scanf("%d", &n) != EOF) {printf("%d\n", fib(n));}return 0;
}