目录😋
任务描述
本关任务:编写递归函数求斐波那契数列的前n项。
相关知识
为了完成本关任务,你需要掌握:
- 递归的概念
- 边界条件的确定
- 循环控制 / 跳转语句的使用
一、递归的概念
1. 递归的定义
- 递归是一种在函数定义中直接或间接地调用自身的编程技巧。它就像是俄罗斯套娃,一个大娃娃里面套着一个小娃娃,小娃娃里面可能还套着更小的娃娃。在编程中,一个函数在执行过程中会调用自身来解决问题。
- 例如,我们定义一个函数来计算一个整数的阶乘。阶乘的数学定义是 编辑,用递归的方式可以这样定义函数:
int factorial(int n) { if (n == 0 || n == 1) { return 1; } else { return n * factorial(n - 1); } }
- 在这里,
factorial
函数在计算n
的阶乘时,如果n
为 0 或者 1,直接返回 1(这是阶乘的边界条件)。如果n
大于 1,就返回n
乘以factorial(n - 1)
,也就是用n
乘以(n - 1)
的阶乘,这就是函数调用自身的过程。2.递归的工作原理(调用栈)
- 当一个函数被调用时,计算机系统会为这个函数分配一块内存空间,称为栈帧。栈帧中存储了函数的参数、局部变量和返回地址等信息。在递归函数中,每次函数调用自身,都会创建一个新的栈帧。
- 以刚才的阶乘函数为例,当计算
factorial(3)
时,首先进入函数,因为3
大于 1,所以要计算3*factorial(2)
。此时,为了计算factorial(2)
,会创建一个新的栈帧,在这个新栈帧中计算factorial(2)
的值。同样,因为2
大于 1,要计算2*factorial(1)
,又会创建一个新栈帧来计算factorial(1)
。当计算factorial(1)
时,根据边界条件,直接返回 1。然后这个返回值会回到计算2*factorial(1)
的地方,得到2*1 = 2
,这个结果又会回到计算3*factorial(2)
的地方,得到3*2 = 6
,这就是factorial(3)
的结果。- 可以把调用栈想象成一叠盘子,每一个新的函数调用就像是在这叠盘子上放一个新盘子,当函数返回时,就相当于从这叠盘子上拿走一个盘子。最上面的盘子(最后进入的函数调用)先被处理,这就是 “后进先出”(LIFO)的原则。
3. 递归的优缺点
- 优点 对于一些具有递归性质的问题,如树的遍历、图的搜索和数学上的递归定义(如斐波那契数列、汉诺塔问题等),递归可以使代码非常简洁和直观。它能够以一种自然的方式来表达问题的解决方案,符合问题本身的逻辑结构。例如,对于二叉树的前序遍历,递归代码如下:
struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; void preorderTraversal(struct TreeNode* root) { if (root == NULL) { return; } printf("%d ", root->val); preorderTraversal(root->left); preorderTraversal(root->right); }
- 这段代码清晰地表达了二叉树前序遍历的顺序:先访问根节点,然后递归地遍历左子树,再递归地遍历右子树
- 缺点
- 递归函数的执行效率可能较低。由于每次函数调用都会创建新的栈帧,过多的函数调用会占用大量的栈空间。如果递归层次过深,可能会导致栈溢出错误。例如,在计算一个很大的数的阶乘时,可能会因为栈空间不足而使程序崩溃。
- 递归函数的理解对于初学者来说可能比较困难。需要清楚地理解函数的调用过程、边界条件和返回值的传递等,否则很容易出现逻辑错误。而且,有些问题虽然可以用递归解决,但可能有更高效的非递归解决方案。
二、边界条件的确定
1. 什么是边界条件
- 在递归函数中,边界条件是递归停止的条件。它是问题的最简单情况,在这种情况下,函数可以直接返回一个已知的结果,而不需要再进行递归调用。可以把边界条件想象成一个 “出口”,当递归过程到达这个 “出口” 时,就停止递归并开始返回结果。
- 以斐波那契数列为例,它的定义是 ,其中 。这里 和 就是边界条件。因为当 n 为 1 或者 2 时,斐波那契数列的值是明确的,不需要通过递归计算前两项来得到。
2. 如何确定边界条件
- 分析问题的最简形式
对于每种需要用递归解决的问题,都要先思考问题的最简情况是什么。比如计算一个整数的阶乘 ,最简情况就是 或者 时,阶乘的值为 1。这是根据阶乘的数学定义确定的,因为 , 。所以在编写阶乘的递归函数时,边界条件就是 或者 。- 观察问题的起始状态或基础情况
例如,在汉诺塔问题中,当只有一个圆盘时,直接将圆盘从起始柱子移动到目标柱子就可以了,这就是汉诺塔问题的边界条件。汉诺塔问题的描述是:有三根柱子 A、B、C,A 柱上有 个圆盘,这些圆盘从上到下是按照从小到大的顺序排列的,要求把所有圆盘从 A 柱移到 C 柱,在移动过程中可以借助 B 柱,并且规定每次只能移动一个圆盘,而且大圆盘不能放在小圆盘上面。当 时,直接将圆盘从 A 柱移动到 C 柱,这就是最基础的情况,也就是边界条件。- 考虑问题的特殊情况或限制条件
比如在一个查找二叉搜索树(BST)中某个值的递归函数中,边界条件包括树为空的情况(表示没有找到目标值)和找到目标值的情况。如果树为空,直接返回空指针或者表示未找到的标记;如果当前节点的值等于目标值,就返回当前节点。这是根据二叉搜索树的性质确定的,因为二叉搜索树的左子树中的所有节点的值都小于根节点的值,右子树中的所有节点的值都大于根节点的值。3. 边界条件错误的后果
- 无限递归
如果没有正确设置边界条件或者边界条件设置错误,很可能会导致函数无限递归。例如,在计算斐波那契数列时,如果忘记了设置 和 的边界条件,函数会一直调用自身,因为没有停止的条件。这会导致栈空间被不断占用,最终导致栈溢出错误,程序崩溃。- 结果错误
即使递归函数没有无限递归,错误的边界条件也可能导致结果错误。例如,在计算阶乘时,如果错误地将边界条件设置为 时返回 2(正确的是返回 1),那么计算出来的阶乘结果就会全部错误。因为递归计算是基于边界条件开始逐步构建结果的,边界条件错误会像多米诺骨牌一样影响后续的计算结果。三、循环控制 / 跳转语句的使用
1. 循环控制语句(for 循环)
- 基本原理:
for
循环是一种常用的循环结构,它允许您指定一个初始化表达式、一个循环条件和一个更新表达式。语法格式为for(初始化表达式; 循环条件; 更新表达式)
。初始化表达式在循环开始时执行一次,用于初始化循环变量。循环条件在每次循环迭代开始时进行检查,如果为真,则执行循环体中的代码。更新表达式在每次循环体执行完后执行,用于更新循环变量。- 示例代码
int main() { // 打印1到10的数字 for (int i = 1; i <= 10; i++) { printf("%d ", i); } printf("\n"); return 0; }
2. 循环控制语句(while 循环)
- 基本原理:
while
循环在循环开始时检查循环条件。只要条件为真,就会执行循环体中的代码。语法格式为while(循环条件)
。循环条件是一个表达式,它返回一个布尔值(真或假)。在循环体中,通常需要包含一些能够改变循环条件的语句,否则可能会导致无限循环。- 示例代码
int main() { int i = 1; while (i <= 10) { printf("%d ", i); i++; } printf("\n"); return 0; }
3. 跳转语句(break 语句)
- 基本原理:
break
语句用于立即跳出当前循环(for
、while
、do - while
)或switch
语句。当程序执行到break
语句时,循环或switch
语句会立即终止,程序控制流将跳转到循环或switch
语句后的下一条语句。- 示例代码(在循环中使用 break)
int main() { for (int i = 1; i <= 10; i++) { if (i == 5) { break; } printf("%d ", i); } printf("\n"); return 0; }
4. 跳转语句(continue 语句)
- 基本原理:
continue
语句用于跳过当前循环迭代的剩余部分,直接开始下一次循环迭代。当程序执行到continue
语句时,循环体中continue
语句之后的代码将不会被执行,而是直接跳转到循环的更新表达式(对于for
循环)或循环条件检查(对于while
和do - while
循环)。- 示例代码(在循环中使用 continue)
int main() { for (int i = 1; i <= 10; i++) { if (i == 5) { continue; } printf("%d ", i); } printf("\n"); return 0; }
编程要求
根据提示在右侧编辑器Begin--End之间的区域内补充必要的代码。
测试说明
平台会对你编写的代码进行测试:
测试输入:
3
预期输出:
1 1 2
测试输入:
5
预期输出:
1 1 2 3 5
开始你的任务吧,祝你成功!
通关代码
int Fib(int n) { //请在此添加代码 /*********Begin*********/ { if(n == 0||n == 1){ return 1; }else{ return Fib(n-1)+Fib(n-2); } } } void PrintfFibSequence(int n){ for(int i = 0;i < n;i++){ printf("%d\n",Fib(i)); } } /********* End *********/ int main() { int n = 0,i; scanf("%d", &n); //请在此添加代码 /*********Begin*********/ PrintfFibSequence(n); /********* End *********/ }
测试结果