递归的使用
目前个人遇到过的几种情况
//不带有任何返回参数的递归，通常闭合条件是内定的
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 函数来计算斐波那契数列中对应位置的数字，并将结果输出。
注意
请注意，递归实现中，递归深度会随着输入值的增加而增加，可能导致堆栈溢出。因此，在实际使用递归时，需要注意递归深度的限制，或者考虑使用迭代方法来替代递归。
递归是一种编程技巧，它可以解决许多问题，但也存在一些优劣之处。
优点：
-
简洁清晰：递归可以将复杂的问题拆分成更小的子问题，使代码结构更加清晰、简洁。
-
可读性强：递归的代码通常具有良好的可读性，因为它可以直接反映问题的本质，使得代码更易于理解和维护。
-
解决特定问题：某些问题天然适合使用递归来解决，例如树结构、图遍历等。
缺点： -
性能开销：递归调用涉及函数的堆栈操作，可能会占用大量的内存和额外的时间。递归深度过大时，可能导致堆栈溢出。
-
可能引发重复计算：某些递归算法可能会重复计算相同的子问题，导致效率低下。可以通过记忆化技术（如动态规划）来解决这个问题。
-
可能导致代码难以理解和调试：过度的递归调用可能导致代码变得复杂，难以理解和调试。在处理复杂问题时，递归的控制流可能变得难以追踪。
注：关于动态规划，后期会逐渐提到
相关资源
以下是一些常用的数据结构可视化网站：
-
Visualgo: https://visualgo.net/zh - 提供了各种数据结构和算法的可视化演示，包括数组、链表、树、图等。
-
Data Structure Visualizations: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html - 提供了多种数据结构和算法的可视化演示，包括栈、队列、堆、排序算法等。
-
Algorithm Visualizer: https://algorithm-visualizer.org/ - 提供了多种数据结构和算法的可视化演示，包括树、排序算法、图算法等。
引入几个，其他功能的网站，如下：
https://www.bejson.com/runcode/cpp920/ 这是一个在线运行代码的网站
https://codebeautify.org/cpp-formatter-beautifier 可以在线美化代码
网友评论