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

简介: 本关任务是编写递归函数求斐波那契数列的前n项。主要内容包括:1. **递归的概念**:递归是一种函数直接或间接调用自身的编程技巧,通过“俄罗斯套娃”的方式解决问题。2. **边界条件的确定**:边界条件是递归停止的条件,确保递归不会无限进行。例如,计算阶乘时,当n为0或1时返回1。3. **循环控制与跳转语句**:介绍`for`、`while`循环及`break`、`continue`语句的使用方法。编程要求是在右侧编辑器Begin--End之间补充代码,测试输入分别为3和5,预期输出为斐波那契数列的前几项。通关代码已给出,需确保正确实现递归逻辑并处理好边界条件,以避免栈溢出或结果

目录😋

任务描述

相关知识

一、递归的概念

1. 递归的定义

2.递归的工作原理(调用栈)

二、边界条件的确定

1. 什么是边界条件

2. 如何确定边界条件

3. 边界条件错误的后果

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

1. 循环控制语句(for 循环)

2. 循环控制语句(while 循环)

3. 跳转语句(break 语句)

4. 跳转语句(continue 语句)

编程要求

测试说明

通关代码

测试结果


任务描述

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


相关知识

为了完成本关任务,你需要掌握:

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

一、递归的概念

1. 递归的定义

  • 递归是一种在函数定义中直接或间接地调用自身的编程技巧。它就像是俄罗斯套娃,一个大娃娃里面套着一个小娃娃,小娃娃里面可能还套着更小的娃娃。在编程中,一个函数在执行过程中会调用自身来解决问题。
  • 例如,我们定义一个函数来计算一个整数的阶乘。阶乘的数学定义是 image.gif 编辑,用递归的方式可以这样定义函数:
int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}
  • image.gif 在这里,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);
}
  • image.gif 这段代码清晰地表达了二叉树前序遍历的顺序:先访问根节点,然后递归地遍历左子树,再递归地遍历右子树
  • 缺点
  • 递归函数的执行效率可能较低。由于每次函数调用都会创建新的栈帧,过多的函数调用会占用大量的栈空间。如果递归层次过深,可能会导致栈溢出错误。例如,在计算一个很大的数的阶乘时,可能会因为栈空间不足而使程序崩溃。
  • 递归函数的理解对于初学者来说可能比较困难。需要清楚地理解函数的调用过程、边界条件和返回值的传递等,否则很容易出现逻辑错误。而且,有些问题虽然可以用递归解决,但可能有更高效的非递归解决方案。

二、边界条件的确定

1. 什么是边界条件

  • 在递归函数中,边界条件是递归停止的条件。它是问题的最简单情况,在这种情况下,函数可以直接返回一个已知的结果,而不需要再进行递归调用。可以把边界条件想象成一个 “出口”,当递归过程到达这个 “出口” 时,就停止递归并开始返回结果。
  • 以斐波那契数列为例,它的定义是 ,其中 。这里 就是边界条件。因为当 n 为 1 或者 2 时,斐波那契数列的值是明确的,不需要通过递归计算前两项来得到。

2. 如何确定边界条件

  • 分析问题的最简形式
    对于每种需要用递归解决的问题,都要先思考问题的最简情况是什么。比如计算一个整数的阶乘 ,最简情况就是 或者 时,阶乘的值为 1。这是根据阶乘的数学定义确定的,因为 。所以在编写阶乘的递归函数时,边界条件就是 或者
  • 观察问题的起始状态或基础情况
    例如,在汉诺塔问题中,当只有一个圆盘时,直接将圆盘从起始柱子移动到目标柱子就可以了,这就是汉诺塔问题的边界条件。汉诺塔问题的描述是:有三根柱子 A、B、C,A 柱上有 个圆盘,这些圆盘从上到下是按照从小到大的顺序排列的,要求把所有圆盘从 A 柱移到 C 柱,在移动过程中可以借助 B 柱,并且规定每次只能移动一个圆盘,而且大圆盘不能放在小圆盘上面。当 时,直接将圆盘从 A 柱移动到 C 柱,这就是最基础的情况,也就是边界条件。
  • 考虑问题的特殊情况或限制条件
    比如在一个查找二叉搜索树(BST)中某个值的递归函数中,边界条件包括树为空的情况(表示没有找到目标值)和找到目标值的情况。如果树为空,直接返回空指针或者表示未找到的标记;如果当前节点的值等于目标值,就返回当前节点。这是根据二叉搜索树的性质确定的,因为二叉搜索树的左子树中的所有节点的值都小于根节点的值,右子树中的所有节点的值都大于根节点的值。

3. 边界条件错误的后果

  • 无限递归
    如果没有正确设置边界条件或者边界条件设置错误,很可能会导致函数无限递归。例如,在计算斐波那契数列时,如果忘记了设置 的边界条件,函数会一直调用自身,因为没有停止的条件。这会导致栈空间被不断占用,最终导致栈溢出错误,程序崩溃。
  • 结果错误
    即使递归函数没有无限递归,错误的边界条件也可能导致结果错误。例如,在计算阶乘时,如果错误地将边界条件设置为 时返回 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;
}
  • image.gif

2. 循环控制语句(while 循环)

  • 基本原理while循环在循环开始时检查循环条件。只要条件为真,就会执行循环体中的代码。语法格式为while(循环条件)。循环条件是一个表达式,它返回一个布尔值(真或假)。在循环体中,通常需要包含一些能够改变循环条件的语句,否则可能会导致无限循环。
  • 示例代码
#include <stdio.h>
int main() {
    int i = 1;
    while (i <= 10) {
        printf("%d ", i);
        i++;
    }
    printf("\n");
    return 0;
}
  • image.gif

3. 跳转语句(break 语句)

  • 基本原理break语句用于立即跳出当前循环(forwhiledo - 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;
}
  • image.gif

4. 跳转语句(continue 语句)

  • 基本原理continue语句用于跳过当前循环迭代的剩余部分,直接开始下一次循环迭代。当程序执行到continue语句时,循环体中continue语句之后的代码将不会被执行,而是直接跳转到循环的更新表达式(对于for循环)或循环条件检查(对于whiledo - 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;
}
  • image.gif

编程要求

根据提示在右侧编辑器Begin--End之间的区域内补充必要的代码。


测试说明

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

测试输入:

3
image.gif

预期输出:

1
1
2
image.gif

测试输入:

5
image.gif

预期输出:

1
1
2
3
5
image.gif

开始你的任务吧,祝你成功!


通关代码

#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 *********/ 
    }

image.gif


测试结果

image.gif

image.gif

目录
相关文章
|
1月前
|
存储 编译器 C语言
【C语言程序设计——函数】分数数列求和2(头歌实践教学平台习题)【合集】
函数首部:按照 C 语言语法,函数的定义首部表明这是一个自定义函数,函数名为fun,它接收一个整型参数n,用于指定要求阶乘的那个数,并且函数的返回值类型为float(在实际中如果阶乘结果数值较大,用float可能会有精度损失,也可以考虑使用double等更合适的数据类型,这里以float为例)。例如:// 函数体代码将放在这里函数体内部变量定义:在函数体中,首先需要定义一些变量来辅助完成阶乘的计算。比如需要定义一个变量(通常为float或double类型,这里假设用float。
37 3
|
1月前
|
存储 算法 安全
【C语言程序设计——函数】分数数列求和1(头歌实践教学平台习题)【合集】
if 语句是最基础的形式,当条件为真时执行其内部的语句块;switch 语句则适用于针对一个表达式的多个固定值进行判断,根据表达式的值与各个 case 后的常量值匹配情况,执行相应 case 分支下的语句,直到遇到 break 语句跳出 switch 结构,若没有匹配值则执行 default 分支(可选)。例如,在判断一个数是否大于 10 的场景中,条件表达式为 “num> 10”,这里的 “num” 是程序中的变量,通过比较其值与 10 的大小关系来确定条件的真假。常量的值必须是唯一的,且在同一个。
20 2
|
1月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
63 23
|
1月前
|
算法 C语言
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数(头歌实践教学平台习题)【合集】
本文档介绍了如何编写两个子函数,分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法(包括辗转相除法和更相减损术),以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明,帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果,确保编程任务的成功完成。
68 15
|
1月前
|
C语言
【C语言程序设计——函数】亲密数判定(头歌实践教学平台习题)【合集】
本文介绍了通过编程实现打印3000以内的全部亲密数的任务。主要内容包括: 1. **任务描述**:实现函数打印3000以内的全部亲密数。 2. **相关知识**: - 循环控制和跳转语句(for、while循环,break、continue语句)的使用。 - 亲密数的概念及历史背景。 - 判断亲密数的方法:计算数A的因子和存于B,再计算B的因子和存于sum,最后比较sum与A是否相等。 3. **编程要求**:根据提示在指定区域内补充代码。 4. **测试说明**:平台对代码进行测试,预期输出如220和284是一组亲密数。 5. **通关代码**:提供了完整的C语言代码实现
61 24
|
1月前
|
存储 编译器 C语言
【C语言程序设计——函数】回文数判定(头歌实践教学平台习题)【合集】
算术运算于 C 语言仿若精密 “齿轮组”,驱动着数值处理流程。编写函数求区间[100,500]中所有的回文数,要求每行打印10个数。根据提示在右侧编辑器Begin--End之间的区域内补充必要的代码。如果操作数是浮点数,在 C 语言中是不允许直接进行。的结果是 -1,因为 -7 除以 3 商为 -2,余数为 -1;注意:每一个数据输出格式为 printf("%4d", i);的结果是 1,因为 7 除以 -3 商为 -2,余数为 1。取余运算要求两个操作数必须是整数类型,包括。开始你的任务吧,祝你成功!
52 1
|
2月前
|
存储 C语言 开发者
【C语言】字符串操作函数详解
这些字符串操作函数在C语言中提供了强大的功能,帮助开发者有效地处理字符串数据。通过对每个函数的详细讲解、示例代码和表格说明,可以更好地理解如何使用这些函数进行各种字符串操作。如果在实际编程中遇到特定的字符串处理需求,可以参考这些函数和示例,灵活运用。
94 10
|
2月前
|
存储 程序员 C语言
【C语言】文件操作函数详解
C语言提供了一组标准库函数来处理文件操作,这些函数定义在 `<stdio.h>` 头文件中。文件操作包括文件的打开、读写、关闭以及文件属性的查询等。以下是常用文件操作函数的详细讲解,包括函数原型、参数说明、返回值说明、示例代码和表格汇总。
69 9
|
2月前
|
存储 Unix Serverless
【C语言】常用函数汇总表
本文总结了C语言中常用的函数,涵盖输入/输出、字符串操作、内存管理、数学运算、时间处理、文件操作及布尔类型等多个方面。每类函数均以表格形式列出其功能和使用示例,便于快速查阅和学习。通过综合示例代码,展示了这些函数的实际应用,帮助读者更好地理解和掌握C语言的基本功能和标准库函数的使用方法。感谢阅读,希望对你有所帮助!
62 8
|
2月前
|
C语言 开发者
【C语言】数学函数详解
在C语言中,数学函数是由标准库 `math.h` 提供的。使用这些函数时,需要包含 `#include <math.h>` 头文件。以下是一些常用的数学函数的详细讲解,包括函数原型、参数说明、返回值说明以及示例代码和表格汇总。
64 6

热门文章

最新文章