【C语言程序设计——函数】递归求斐波那契数列的前n项（头歌实践教学平台习题）【合集】

任务描述

本关任务：编写递归函数求斐波那契数列的前n项。

相关知识

为了完成本关任务，你需要掌握：

1. 递归的概念
2. 边界条件的确定
3. 循环控制 / 跳转语句的使用

一、递归的概念

1. 递归的定义

递归是一种在函数定义中直接或间接地调用自身的编程技巧。它就像是俄罗斯套娃，一个大娃娃里面套着一个小娃娃，小娃娃里面可能还套着更小的娃娃。在编程中，一个函数在执行过程中会调用自身来解决问题。

例如，我们定义一个函数来计算一个整数的阶乘。阶乘的数学定义是

n! = n(n-1)\times (n-2)\times...\times1

，用递归的方式可以这样定义函数：

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. 什么是边界条件

• 在递归函数中，边界条件是递归停止的条件。它是问题的最简单情况，在这种情况下，函数可以直接返回一个已知的结果，而不需要再进行递归调用。可以把边界条件想象成一个 “出口”，当递归过程到达这个 “出口” 时，就停止递归并开始返回结果。
• 以斐波那契数列为例，它的定义是

F(2)=F(n-1)+F(n+2)[n>2]

，其中

F(1)=F(2)=1

。这里

n=1

和

n=2

就是边界条件。因为当 n 为 1 或者 2 时，斐波那契数列的值是明确的，不需要通过递归计算前两项来得到。

2. 如何确定边界条件

• 分析问题的最简形式 对于每种需要用递归解决的问题，都要先思考问题的最简情况是什么。比如计算一个整数的阶乘

n!

，最简情况就是

n=0

或者

n=1

时，阶乘的值为 1。这是根据阶乘的数学定义确定的，因为

0!=1

，

1!=1

。所以在编写阶乘的递归函数时，边界条件就是

n=0

或者

n=1

。

• 观察问题的起始状态或基础情况 例如，在汉诺塔问题中，当只有一个圆盘时，直接将圆盘从起始柱子移动到目标柱子就可以了，这就是汉诺塔问题的边界条件。汉诺塔问题的描述是：有三根柱子 A、B、C，A 柱上有

n

个圆盘，这些圆盘从上到下是按照从小到大的顺序排列的，要求把所有圆盘从 A 柱移到 C 柱，在移动过程中可以借助 B 柱，并且规定每次只能移动一个圆盘，而且大圆盘不能放在小圆盘上面。当

n=1

时，直接将圆盘从 A 柱移动到 C 柱，这就是最基础的情况，也就是边界条件。

• 考虑问题的特殊情况或限制条件 比如在一个查找二叉搜索树（BST）中某个值的递归函数中，边界条件包括树为空的情况（表示没有找到目标值）和找到目标值的情况。如果树为空，直接返回空指针或者表示未找到的标记；如果当前节点的值等于目标值，就返回当前节点。这是根据二叉搜索树的性质确定的，因为二叉搜索树的左子树中的所有节点的值都小于根节点的值，右子树中的所有节点的值都大于根节点的值。

3. 边界条件错误的后果

• 无限递归 如果没有正确设置边界条件或者边界条件设置错误，很可能会导致函数无限递归。例如，在计算斐波那契数列时，如果忘记了设置

n=1

和

n=2

的边界条件，函数会一直调用自身，因为没有停止的条件。这会导致栈空间被不断占用，最终导致栈溢出错误，程序崩溃。

• 结果错误 即使递归函数没有无限递归，错误的边界条件也可能导致结果错误。例如，在计算阶乘时，如果错误地将边界条件设置为

n=2

时返回 2（正确的是返回 1），那么计算出来的阶乘结果就会全部错误。因为递归计算是基于边界条件开始逐步构建结果的，边界条件错误会像多米诺骨牌一样影响后续的计算结果。

三、循环控制 / 跳转语句的使用

1. 循环控制语句（for 循环）

基本原理：for循环是一种常用的循环结构，它允许您指定一个初始化表达式、一个循环条件和一个更新表达式。语法格式为for(初始化表达式; 循环条件; 更新表达式)。初始化表达式在循环开始时执行一次，用于初始化循环变量。循环条件在每次循环迭代开始时进行检查，如果为真，则执行循环体中的代码。更新表达式在每次循环体执行完后执行，用于更新循环变量。

示例代码

#include <stdio.h>
int main() {
    // 打印1到10的数字
    for (int i = 1; i <= 10; i++) {
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}

2. 循环控制语句（while 循环）

基本原理：while循环在循环开始时检查循环条件。只要条件为真，就会执行循环体中的代码。语法格式为while(循环条件)。循环条件是一个表达式，它返回一个布尔值（真或假）。在循环体中，通常需要包含一些能够改变循环条件的语句，否则可能会导致无限循环。

示例代码

#include <stdio.h>
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）

#include <stdio.h>
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）

#include <stdio.h>
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

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

通关代码

#include<stdio.h>
 
	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 *********/ 
	}

测试结果