C++U3-第08课-递归函数-526互联

递归是一种算法设计和编程技巧，其中函数在其定义中调用自身。换句话说，递归是通过将一个问题分解为更小的子问题来解决问题的方法。

递归算法通常包含两个部分：基本情况（base case）和递归情况（recursive case）。基本情况是递归函数停止递归并返回结果的条件。递归情况是指递归函数调用自身以解决更小规模的同一问题。

递归算法的执行过程如下：

当遇到基本情况时，递归函数直接返回结果。
否则，递归函数调用自身，并将问题分解为更小规模的子问题。
递归函数继续执行，直到达到基本情况。

递归算法可以使问题变得更简洁和易于理解，尤其在处理具有重复性结构的问题时。它常用于树、图、排列组合等领域的问题，例如树的遍历、阶乘计算、斐波那契数列等。

然而，递归算法需要注意递归深度和性能问题。如果递归深度过大或递归过程中没有有效的剪枝操作，可能会导致堆栈溢出或性能下降。因此，在使用递归算法时，需要仔细设计和评估其效率，并确保递归过程能够终止。

学习目标

递归的概念

递归的两个要素

递归函数练习

task1

task2

[【递归】倒序输出]

#include <iostream>
using namespace std;

// 递归函数用于输出每一位数字
void output(long long n, int digit) {
    if (digit == 1) { // 当只剩最后一位数字时，直接输出
        cout << n;
        return;
    }
    cout << n % 10; // 取最后一位数字并输出
    output(n / 10, digit - 1); // 递归处理剩余位数
}

int main() {
    long long n;
    cin >> n; // 输入一个整数

    int digit = 0; // 位数计数器
    long long m = n;
    while (m > 0) { // 计算输入整数的位数
        digit++;
        m /= 10;
    }

    output(n, digit); // 调用函数输出每一位数字

    return 0;
}


此代码利用递归函数 output 来输出给定整数的每一位数字。在 main 函数中，首先读取一个整数 n。然后通过循环计算 n 的位数，并将结果存储在 digit 变量中。最后调用 output 函数，将 n 和位数 digit 作为参数传递给该函数来递归地输出每一位数字。

请注意，这段代码假设输入的整数是正数，并且不考虑负号。如果需要处理负数，请在输入前进行相应的处理或在代码中添加适当的逻辑。

View Code

递归思维汉诺塔问题

初赛知识

【思路分析】
采用递归，dfs(x) 的里输出 x 转化成的二进制数的最后一位，由于最终得到的余数要逆序输出，则应当先递归在进行输出，递归终止条件是 x=0。

1、定义变量 n

2、输入变量 n

3、递归进行处理解决

 3.1、十进制转化为二进制的整体思想：除2取余，余数逆序排列

 3.2、递归的结束条件

 3.3、余数逆序，应该先递归在输出

【参考代码】
#include <iostream>
using namespace std;
void dfs(int x)
{
    //3.1、十进制转化为二进制的整体思想：除2取余,余数逆序排列 
    //3.2、递归的结束条件 
    if (x == 0)
        return;
    //3.3、余数逆序，应该先递归在输出 
    dfs(x / 2);
    cout << x % 2;
}
int main()
{
    //1、定义变量 n 
    int n;
    //2、输入变量 n 
    cin >> n;
    //3、递归进行处理解决 
    dfs(n);
    return 0;
}

View Code

u3dframeworkdemo 3dframeworkdemo dframeworkdemo