7.递归函数

编程语言 > CPP > CPP基础 > CPP基础语法知识编程语言 CPP CPP基础函数 CPP基础语法知识

发布时间 : 2025-01-20 13:02

字数:1.8k 阅读 :

评论:

7.函数-递归函数

7.函数-递归函数

7.1 知识点

基本概念

递归函数就是让函数自己调用自己。

void fun()
{
    if (/*递归停止的条件*/)
    {
        return;
    }
    fun();
}

一个正确的递归函数：

必须要有一个结束调用的条件。
递归停止的条件往往是变化的，在递归函数执行过程中变化，当变化满足一定条件时，就会触发停止执行。

实例

使用递归函数打印出 0 到 10。

声明：

void fun(int num);

定义：

// 递归函数是自己调用自己
// fun(0) - 打印 0 变为 1
// fun(1) - 打印 1 变为 2
// ...
// fun(10) - 打印 10 变为 11
// fun(11) - return
void fun(int num)
{
    // 第四步：结束条件
    if (num > 10)
        return;
    
    // 第二步：完成题目要求，打印一个数
    cout << num << endl;
    
    // 第三步：完成题目要求，能够打印出 0~10 了，只不过它不仅能打印出 0~10，还能打印更多
    ++num;
    
    // 第一步：构造一个递归函数
    fun(num);
}

使用：

fun(0);

输出：

7.2 知识点代码

Lesson07_函数_递归函数.cpp

#include <iostream>
using namespace std;

void fun(int num);

int main()
{
    std::cout << "递归函数\n";

    fun(0);
    //0
    //1
    //2
    //3
    //4
    //5
    //6
    //7
    //8
    //9
    //10
}

#pragma region 知识点一 基本概念

//递归函数 就是 让函数自己调用自己
//void fun()
//{
//    if (/*递归停止的条件*/)
//    {
//        return;
//    }
//    fun();
//}
//一个正确的递归函数
//1.必须要有一个结束调用的条件
//2.递归停止的条件 往往是变化的 是在递归函数执行过程中变化的 当变化满足一定条件 就会触发停止执行

#pragma endregion

#pragma region 知识点二 实例

//用递归函数打印出 0到10

//递归函数 是自己调自己
//fun(0) - 打印0 变为1
//fun(1) - 打印1 变为2
//....
//fun(10) - 打印10 变为11
//fun(11) - return
void fun(int num)
{
    //第四步：结束条件
    if (num > 10)
        return;
    //第二步：完成题目要求 打印一个数
    cout << num << endl;
    //第三步：完成题目要求 能够打印出0~10了 只不过 它不仅能打印出0~10 还能打印更多
    ++num;
    //第一步：构造一个递归函数
    fun(num);
}

#pragma endregion

7.3 练习题

使用递归的方式打印0~10

void func(int num)
{
    if (num > 10)
        return;
    cout << num << endl;
    ++num;
    func(num);
}

传入一个值，递归求该值的阶乘并返回5! = 12345

int func2(int num)
{
    //递归结束条件 传入的是1
    //就直接结束 返回1即可
    if (num == 1)
        return 1;

    // num! = 1 * 2 * 3 * 4 * 5 * ..... num
    //5!= 1 * 2 * 3 * 4 * 5
    // num! = num * num -1 * ....... 2 * 1
    //5!= 5 * 4 * 3 * 2 * 1

    // 5 * func2(4) = 5 * (4 * 3 * 2 * 1)
    // 4 * func2(3) = 4 * (3 * 2 * 1)
    // 3 * func2(2) = 3 * (2 * 1)
    // 2 * func2(1) = 2 * (1)
    // 1 - 当传入的是1的时候 就是结束的时候
    return num * func2(num - 1);
}

使用递归求1! + 2! + 3! + 4! + ….. + 10!

// func2(1) + func2(2) + func2(3) ...... func2(10)
// func2(10) + func2(9) + func2(8)..... func2(1)
int func3(int num)
{
    //当传入的num为1时 证明就直接返回1的阶乘即可 相当于是最后一步了
    if (num == 1)
        return func2(1);

    //阶乘(10) + 阶乘(9) + 阶乘(8) ...... 阶乘(2) + 阶乘(1)
    return func2(num) + func3(num - 1);
    //阶乘(10) + func3(9) = 阶乘(10) + 阶乘(9) + 阶乘(8) + .... + 乘(2) + 阶乘(1)
    //阶乘(9) + func3(8) = 阶乘(9) + 阶乘(8) + 阶乘(7) + .... + 乘(2) + 阶乘(1)
    //阶乘(8) + func3(7) = 阶乘(8) + 阶乘(7) + 阶乘(6) + .... + 乘(2) + 阶乘(1)
    //.....
    //阶乘(2) + func3(1) = 阶乘(2) + 阶乘(1)
    //阶乘(1)
}

一根竹竿长100m，每天砍掉一半，求第十天它的长度是多少（从第0天开始）

//当天数为10时 则是结束的时刻（要返回内容的时刻）
//func4(100, 0) = 50
//func4(50, 1) = 25
//func4(25, 2) = 12.5
//func4(12.5, 3) = 6.25
//func4(6.25, 4) = 3.125
//func4(3.125, 5) = 1.5625
//func4(1.5625, 6) = 0.78125
//func4(0.78125, 7) = 0.390625
//func4(0.390625, 8) = 0.1953125
//func4(0.1953125, 9) = 0.09765625
void func4(float length, int day)
{
    //每天砍掉一半
    length /= 2;
    //当前砍了过后 去判断 是不是第10天 如果是 就应该停下得到结果了
    if (day == 9)
    {
        cout << "第十天砍完后的竹子长" << length << "米" << endl;
        return;
    }
    //看一半 就过一天
    ++day;
    func4(length, day);
}

不允许使用循环语句、条件语句，在控制台中打印出1-200这200个数（提示：递归+短路）

bool func5(int num)
{
    cout << num << endl;
    return num == 200 || func5(num + 1);
}

7.4 练习题代码

Lesson07_练习题.cpp

#include <iostream>
using namespace std;

void func(int num);
int func2(int num);
int func3(int num);
void func4(float length = 100, int day = 0);
bool func5(int num);

int main()
{
    std::cout << "递归练习题\n";

    func(0);

    cout << func2(6) << endl;

    cout << func3(10) << endl;

    func4();

    func5(1);
}

#pragma region 练习题一

//使用递归的方式打印0~10

void func(int num)
{
    if (num > 10)
        return;
    cout << num << endl;
    ++num;
    func(num);
}

#pragma endregion

#pragma region 练习题二

//传入一个值，递归求该值的阶乘 并返回
//5!= 1 * 2 * 3 * 4 * 5

int func2(int num)
{
    //递归结束条件 传入的是1
    //就直接结束 返回1即可
    if (num == 1)
        return 1;

    // num! = 1 * 2 * 3 * 4 * 5 * ..... num
    //5!= 1 * 2 * 3 * 4 * 5
    // num! = num * num -1 * ....... 2 * 1
    //5!= 5 * 4 * 3 * 2 * 1
    
    // 5 * func2(4) = 5 * (4 * 3 * 2 * 1)
    // 4 * func2(3) = 4 * (3 * 2 * 1)
    // 3 * func2(2) = 3 * (2 * 1)
    // 2 * func2(1) = 2 * (1)
    // 1 - 当传入的是1的时候 就是结束的时候
    return num * func2(num - 1);
}

#pragma endregion

#pragma region 练习题三

//使用递归求 1!+ 2!+ 3!+ 4!+ ..... + 10!

// func2(1) + func2(2) + func2(3) ...... func2(10)
// func2(10) + func2(9) + func2(8)..... func2(1)
int func3(int num)
{
    //当传入的num为1时 证明就直接返回1的阶乘即可 相当于是最后一步了
    if (num == 1)
        return func2(1);

    //阶乘(10) + 阶乘(9) + 阶乘(8) ...... 阶乘(2) + 阶乘(1)
    return func2(num) + func3(num - 1);
    //阶乘(10) + func3(9) = 阶乘(10) + 阶乘(9) + 阶乘(8) + .... + 乘(2) + 阶乘(1)
    //阶乘(9) + func3(8) = 阶乘(9) + 阶乘(8) + 阶乘(7) + .... + 乘(2) + 阶乘(1)
    //阶乘(8) + func3(7) = 阶乘(8) + 阶乘(7) + 阶乘(6) + .... + 乘(2) + 阶乘(1)
    //.....
    //阶乘(2) + func3(1) = 阶乘(2) + 阶乘(1)
    //阶乘(1)
}

#pragma endregion

#pragma region 练习题四

//一根竹竿长100m，每天砍掉一半，求第十天它的长度是多少（从第0天开始）

//当天数为10时 则是结束的时刻（要返回内容的时刻）
//func4(100, 0) = 50
//func4(50, 1) = 25
//func4(25, 2) = 12.5
//func4(12.5, 3) = 6.25
//func4(6.25, 4) = 3.125
//func4(3.125, 5) = 1.5625
//func4(1.5625, 6) = 0.78125
//func4(0.78125, 7) = 0.390625
//func4(0.390625, 8) = 0.1953125
//func4(0.1953125, 9) = 0.09765625
void func4(float length, int day)
{
    //每天砍掉一半
    length /= 2;
    //当前砍了过后 去判断 是不是第10天 如果是 就应该停下得到结果了
    if (day == 9)
    {
        cout << "第十天砍完后的竹子长" << length << "米" << endl;
        return;
    }
    //看一半 就过一天
    ++day;
    func4(length, day);
}
 
#pragma endregion

#pragma region 练习题五

//不允许使用循环语句、条件语句，在控制台中打印出1 - 200这200个数（提示：递归 + 短路）

bool func5(int num)
{
    cout << num << endl;
    return num == 200 || func5(num + 1);
}

#pragma endregion

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com