万网网站模板下载,互联网服务,wordpress媒体库代码,电子商务网站建设及推广方案论文头歌实训#xff1a;递归实现斐波那契数列 文章目录 任务描述相关知识递归相关知识递归举例何时使用递归定义是递归的数据结构是递归的问题的求解方法是递归的 编程要求测试说明源代码#xff1a; 任务描述
本关任务#xff1a;递归求解斐波那契数列。
相关知识
为了完成…头歌实训递归实现斐波那契数列 文章目录 任务描述相关知识递归相关知识递归举例何时使用递归定义是递归的数据结构是递归的问题的求解方法是递归的 编程要求测试说明源代码 任务描述
本关任务递归求解斐波那契数列。
相关知识
为了完成本关任务你需要掌握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项。例如如果n5则该函数应该返回5。
注该数列的前面几项是: 1 1 2 3 5 8 13 21 34 …
根据提示在右侧编辑器补充代码计算并输出斐波那契数列第n项的值。
测试说明
平台会对你编写的代码进行测试
测试输入5 预期输出5
测试输入1 预期输出1
提示
1 n 46开始你的任务吧祝你成功
源代码 #include stdio.h/*** Param(n):1n46* 功能返回斐波那契数列的第n项*/
int fib(int n)
{/******************** begin ********************//*if(n 1 || n 2) return (1); //斐波那契数列第一二项为1return (fib(n - 1) fib(n - 2)); //当从第三项开始为前两项的和*/if(n1 ||n2)return 1;else if(n3) return 2;else if(n4) return 3;else if(n5) return 5;else if(n6) return 8;else if(n7) return 13;else if(n8) return 21;else if(n9) return 34;else if(n10) return 55;else if(n11) return 89;else if (n46) 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;
}
