递归的使用

目前个人遇到过的几种情况

//不带有任何返回参数的递归，通常闭合条件是内定的
void Fun(T* tObj)
{
    if(/*some case*/)
    {
        Fun(newObj);
    }
}

//没有返回参数，但是可以通过一个递归外的量作为退出条件，或作为回收统计机制
void Fun(T* tObj,T2& set1,T3& set2)
{
     if(/*some case*/)
    {
        Fun(newObj, set1, set2);
    }
}

//具备返回值的递归
int Fun(T* a,T* b)
{
    return Fun(a->left, a->right) + Fun(b->left, b->right);
}

其他一些递归的案例

阶乘计算

计算一个正整数的阶乘。例如，n! = n * (n-1) * (n-2) * ... * 1。可以使用递归来计算阶乘，通过将问题分解为更小的子问题。

当计算一个正整数的阶乘时，可以使用递归实现。下面是一个示例代码，演示了如何使用递归来计算阶乘：

#include <iostream>

unsigned long long factorial(unsigned int n) {
    // 递归终止条件：当 n 为 0 或 1 时，阶乘为 1
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // 递归调用，将问题分解为较小的子问题
    return n * factorial(n - 1);
}

int main() {
    unsigned int num;

    std::cout << "Enter a positive integer: ";
    std::cin >> num;

    unsigned long long result = factorial(num);
    std::cout << "Factorial of " << num << " is " << result << std::endl;

    return 0;
}

在上述代码中，factorial 函数使用递归方式计算阶乘。当 n 为 0 或 1 时，递归终止，直接返回 1。否则，递归调用 factorial 函数来计算 (n-1) 的阶乘，并将结果乘以 n，得到 n! 的值。在 main 函数中，用户输入一个正整数，然后调用 factorial 函数来计算其阶乘，并将结果输出。

斐波那契数列

计算斐波那契数列的第 n 个数字。斐波那契数列的定义是，前两个数字是 0 和 1，后续的数字是前两个数字的和。可以使用递归来计算斐波那契数列，通过将问题分解为两个较小的子问题。下面是一个示例代码，展示了如何使用递归来计算斐波那契数列的第 n 个数字：

#include <iostream>

unsigned long long fibonacci(unsigned int n) {
    // 递归终止条件：当 n 为 0 或 1 时，斐波那契数为 n
    if (n == 0 || n == 1) {
        return n;
    }
    
    // 递归调用，将问题分解为两个较小的子问题
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    unsigned int num;

    std::cout << "Enter a positive integer: ";
    std::cin >> num;

    unsigned long long result = fibonacci(num);
    std::cout << "Fibonacci number at position " << num << " is " << result << std::endl;

    return 0;
}

在上述代码中，fibonacci 函数使用递归方式计算斐波那契数列的第 n 个数字。当 n 为 0 或 1 时，递归终止，直接返回 n。否则，递归调用 fibonacci 函数来计算第 n-1 和 n-2 个数字的斐波那契数，并将两者相加得到第 n 个数字。在 main 函数中，用户输入一个正整数，然后调用 fibonacci 函数来计算斐波那契数列中对应位置的数字，并将结果输出。

注意

请注意，递归实现中，递归深度会随着输入值的增加而增加，可能导致堆栈溢出。因此，在实际使用递归时，需要注意递归深度的限制，或者考虑使用迭代方法来替代递归。

递归是一种编程技巧，它可以解决许多问题，但也存在一些优劣之处。

优点：

1. 简洁清晰：递归可以将复杂的问题拆分成更小的子问题，使代码结构更加清晰、简洁。

2. 可读性强：递归的代码通常具有良好的可读性，因为它可以直接反映问题的本质，使得代码更易于理解和维护。

3. 解决特定问题：某些问题天然适合使用递归来解决，例如树结构、图遍历等。
   缺点：

4. 性能开销：递归调用涉及函数的堆栈操作，可能会占用大量的内存和额外的时间。递归深度过大时，可能导致堆栈溢出。

5. 可能引发重复计算：某些递归算法可能会重复计算相同的子问题，导致效率低下。可以通过记忆化技术（如动态规划）来解决这个问题。

6. 可能导致代码难以理解和调试：过度的递归调用可能导致代码变得复杂，难以理解和调试。在处理复杂问题时，递归的控制流可能变得难以追踪。

注：关于动态规划，后期会逐渐提到

相关资源

以下是一些常用的数据结构可视化网站：

1. Visualgo: https://visualgo.net/zh - 提供了各种数据结构和算法的可视化演示，包括数组、链表、树、图等。

2. Data Structure Visualizations: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html - 提供了多种数据结构和算法的可视化演示，包括栈、队列、堆、排序算法等。

3. Algorithm Visualizer: https://algorithm-visualizer.org/ - 提供了多种数据结构和算法的可视化演示，包括树、排序算法、图算法等。

引入几个，其他功能的网站，如下：

https://www.bejson.com/runcode/cpp920/ 这是一个在线运行代码的网站
https://codebeautify.org/cpp-formatter-beautifier 可以在线美化代码