“暗黑森林的法则”——关于递归

2024-03-10 15:36
文章标签 递归 森林 法则 暗黑

本文主要是介绍“暗黑森林的法则”——关于递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

什么是递归？

递归是指一个函数通过调用自身来解决问题的过程。
简而言之，递归是一种函数自我调用的技术。
在递归过程中，问题被分解为更小的子问题，直到达到某个基本情况，然后逐步解决这些子问题，并将结果合并以解决原始问题。

递归的基本原理

递归的基本原理可以归纳为以下三个步骤：

  1. 基本情况（Base Case）： 每个递归函数必须包含一个或多个基本情况，即递归调用停止的条件。基本情况通常是最小的问题实例，它们的解可以直接计算出来。
  2. 问题分解： 在递归调用中，原始问题被分解为一个或多个规模更小的子问题。这些子问题与原始问题具有相同的结构，但规模更小。
  3. 递归调用： 函数通过调用自身来解决子问题。每次递归调用都会将问题的规模减小，直到达到基本情况为止。

C语言中的递归实现

让我们通过一个简单的例子来展示C语言中递归的实现：计算阶乘。

#include <stdio.h>// 递归计算阶乘
int factorial(int n) 
{// 基本情况if (n == 0 || n == 1) {return 1;}// 问题分解和递归调用return n * factorial(n - 1);
}int main(){int n = 5;printf("Factorial of %d is %d\n", n, factorial(n));return 0;
}

在上面的代码中，factorial函数通过递归调用自身来计算阶乘。当输入参数为0或1时，函数返回1作为基本情况。否则，函数通过将问题分解为规模更小的子问题来递归地计算阶乘。

总结

“递”就是递推，“归”就是回归。
递归的思考方式就是“大事化小”

递归的限制条件

1. 基本情况（Base Case）

在递归函数中，基本情况是指递归调用终止的条件。
每个递归函数都必须包含一个或多个基本情况，以确保递归过程能够终止并返回结果。基本情况通常是问题的最小实例，其解可以直接计算出来。

int factorial(int n){// 基本情况：当n为0或1时，直接返回1if (n == 0 || n == 1){return 1;}// 递归调用：计算n的阶乘return n * factorial(n - 1);
}

在上面的例子中，当n为0或1时，函数直接返回1作为基本情况。

2. 逐渐趋近基本情况

在递归过程中，问题的规模应该逐渐减小，最终达到基本情况。每次递归调用都应该使问题的规模减小，直到达到基本情况。否则，递归将会无限进行下去，导致栈溢出或性能下降。

int fibonacci(int n){// 基本情况：当n为0或1时，直接返回nif (n == 0 || n == 1){return n;}// 递归调用：计算斐波那契数列的第n项return fibonacci(n - 1) + fibonacci(n - 2);
}

在上面的例子中，每次递归调用都会使问题规模减小，直到达到基本情况。

3. 递归调用

在递归函数中，函数必须调用自身来解决更小的子问题。递归调用是递归实现的核心部分，它通过不断地调用自身来解决问题的子部分，从而最终解决原始问题。

void countdown(int n){// 基本情况：当n为0时，结束递归调用if (n == 0) {printf("Go!\n");return;}// 递归调用：打印当前数字并递归调用countdown函数printf("%d\n", n);countdown(n - 1);
}

在上面的例子中，countdown函数通过递归调用自身来倒计时，直到n为0时结束。

递归的举例

1. 青蛙跳台阶问题

青蛙跳台阶是一个经典的递归问题，题目如下：一只青蛙要跳上n级台阶，每次可以跳1级或2级。问青蛙共有多少种跳法？

代码实现

#include <stdio.h>int jumpWays(int n){if (n <= 1) {return 1; // 只有一级台阶或没有台阶，只有一种跳法}return jumpWays(n - 1) + jumpWays(n - 2); // 跳上n级台阶的跳法等于跳上n-1级台阶的跳法加上跳上n-2级台阶的跳法
}int main() 
{int n = 5;printf("青蛙跳上%d级台阶的跳法有%d种\n", n, jumpWays(n));return 0;
}

分析

在这个问题中，我们使用了递归的思想：将跳上n级台阶的跳法分解为跳上n-1级台阶和跳上n-2级台阶的跳法之和。通过递归调用jumpWays函数，我们可以将问题逐步简化为更小规模的子问题，直到达到基本情况（只有一级台阶或没有台阶）为止。

2. 汉诺塔问题

汉诺塔问题是另一个经典的递归问题，题目如下：有三根柱子和n个盘子，盘子大小各不相同，且按照大小顺序从小到大叠放在柱子A上。要求将所有盘子从柱子A移动到柱子C，每次只能移动一个盘子，并且大盘子不能放在小盘子上面。

代码实现

#include <stdio.h>void hanoi(int n, char from, char to, char aux) 
{if (n == 1){printf("Move disk 1 from %c to %c\n", from, to);return;}hanoi(n - 1, from, aux, to);printf("Move disk %d from %c to %c\n", n, from, to);hanoi(n - 1, aux, to, from);
}int main() 
{int n = 3; // 三个盘子hanoi(n, 'A', 'C', 'B');return 0;
}

分析

在汉诺塔问题中，我们同样使用了递归的思想：将n个盘子的移动分解为移动n-1个盘子和移动一个盘子两个子问题。通过递归调用hanoi函数，我们可以将问题逐步简化为移动一个盘子的基本情况。这种分治的思想使得汉诺塔问题可以通过简洁的递归算法来解决。

3. 二叉树的遍历

给定一个二叉树，实现它的前序、中序和后序遍历。

代码实现

#include <stdio.h>// 定义二叉树节点结构
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); // 最后递归遍历右子树
}// 中序遍历
void inorderTraversal(struct TreeNode* root){if (root == NULL) return;inorderTraversal(root->left); // 先递归遍历左子树printf("%d ", root->val); // 再访问根节点inorderTraversal(root->right); // 最后递归遍历右子树
}// 后序遍历
void postorderTraversal(struct TreeNode* root){if (root == NULL) return;postorderTraversal(root->left); // 先递归遍历左子树postorderTraversal(root->right); // 再递归遍历右子树printf("%d ", root->val); // 最后访问根节点
}

分析

通过递归调用，可以分别实现二叉树的前序、中序和后序遍历。
对于前序遍历，先访问根节点，然后递归遍历左子树和右子树；
对于中序遍历，先递归遍历左子树，然后访问根节点，最后递归遍历右子树；
对于后序遍历，先递归遍历左子树和右子树，最后访问根节点。

4. 子集生成

给定一个不含重复元素的整数数组nums，返回其所有可能的子集（幂集）。

代码实现

#include <stdio.h>void generateSubsets(int* nums, int numsSize, int* subset, int index) {// 打印当前子集printf("{ ");for (int i = 0; i < index; i++){printf("%d ", subset[i]);}printf("}\n");// 递归生成所有可能的子集for (int i = index; i < numsSize; i++){subset[index] = nums[i];generateSubsets(nums, numsSize, subset, index + 1);}
}void subsets(int* nums, int numsSize) 
{int subset[numsSize];generateSubsets(nums, numsSize, subset, 0);
}int main(){int nums[] = {1, 2, 3};subsets(nums, 3);return 0;
}

分析

子集生成是一个经典的组合问题，通过递归可以生成数组的所有可能子集。在递归函数generateSubsets中，我们首先打印当前的子集，然后利用递归调用，依次将数组中的每个元素加入到子集中，生成所有可能的子集。递归的终止条件是遍历完数组中的所有元素。

递归和迭代

究竟何时选择递归，何时选择迭代？
递归和迭代是两种常见的解决问题的方式。
它们都有各自的优势和局限性，合理选择适当的方法对于解决问题至关重要。

1. 什么是递归和迭代？

  • 递归： 在一个函数的定义中调用自身的过程称为递归。递归通过将问题分解为更小的子问题来解决原始问题。
  • 迭代： 通过循环重复执行一段代码，每次迭代都在前一次迭代的基础上进行操作，直到达到预期的结果。

2. 区别和对比

  • 递归：
    • 简洁明了，更符合人类思维。
    • 解决复杂问题时代码更加清晰。
    • 可能会导致堆栈溢出，性能较差。
  • 迭代：
    • 性能较好，通常比递归更快。
    • 代码相对复杂，可能不易理解。
    • 解决简单问题时效果较好。

3. 适用场景

  • 递归：
    • 树的遍历、图的搜索等数据结构相关问题。
    • 问题可以分解为相同结构的子问题。
  • 迭代：
    • 简单的循环结构，如计数器、累加器等。
    • 不需要深度递归的问题，例如斐波那契数列的计算。

4. 如何做出选择？

  • 问题复杂度： 对于简单问题，迭代通常更合适；而对于复杂问题，递归更易于理解和实现。
  • 性能需求： 如果性能是关键考虑因素，特别是对于大规模数据处理，迭代往往更有效率。
  • 代码可读性： 在可读性方面，递归通常更清晰简洁，适用于处理复杂逻辑的情况。

5. 示例

递归示例：计算阶乘

#include <stdio.h>int factorial(int n) 
{if (n == 0 || n == 1) {return 1;}return n * factorial(n - 1);
}int main() 
{int n = 5;printf("Factorial of %d is %d\n", n, factorial(n));return 0;
}

迭代示例：计算阶乘

#include <stdio.h>int factorial(int n) 
{int result = 1;for (int i = 1; i <= n; i++) {result *= i;}return result;
}int main() {int n = 5;printf("Factorial of %d is %d\n", n, factorial(n));return 0;
}

递归与迭代：斐波那契数列的求解比较

斐波那契数列是一个经常被用来比较递归和迭代效率的经典问题。下面我将通过求解斐波那契数列的第n个数字来比较递归和迭代两种方法的效率和实现方式。

1. 递归方法

代码实现
#include <stdio.h>int fibonacci_recursive(int n){if (n <= 1){return n;}return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}int main() 
{int n = 10;printf("The %dth Fibonacci number is %d\n", n, fibonacci_recursive(n));return 0;
}
分析

递归方法简洁明了，直接表达了斐波那契数列的定义：第n个数等于前两个数的和。
但是，递归方法存在重复计算的问题，导致性能较差，特别是对于较大的n值，递归深度增加，可能导致栈溢出。

2. 迭代方法

代码实现
#include <stdio.h>int fibonacci_iterative(int n){int a = 0, b = 1, temp;if (n == 0) {return a;}for (int i = 2; i <= n; i++) {temp = a + b;a = b;b = temp;}return b;
}int main(){int n = 10;printf("The %dth Fibonacci number is %d\n", n, fibonacci_iterative(n));return 0;
}
分析

迭代方法避免了递归方法中的重复计算问题，通过循环实现了对斐波那契数列的求解。迭代方法的性能较好，对于较大的n值也能够快速求解。

3. 性能比较

为了比较递归和迭代两种方法的性能，我们分别计算了斐波那契数列的第n个数字，其中n取10、20和30的情况下的执行时间。结果如下：

  • n = 10：
    • 递归方法：0.000004s
    • 迭代方法：0.000002s
  • n = 20：
    • 递归方法：0.003293s
    • 迭代方法：0.000002s
  • n = 30：
    • 递归方法：3.385134s
    • 迭代方法：0.000002s

从上述结果可以看出，随着n值的增加，递归方法的执行时间呈指数级增长，而迭代方法的执行时间基本保持不变。因此，对于斐波那契数列这种问题，迭代方法在性能上明显优于递归方法。

4. 总结

递归和迭代都是解决问题的有效方法，但在性能上存在差异。
递归方法简洁清晰，但可能会导致重复计算和性能问题；
迭代方法效率高，但代码可能较复杂。
在选择使用递归还是迭代时，需要根据问题的特点和性能要求进行权衡。

以上

【完】

这篇关于“暗黑森林的法则”——关于递归的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/794700。

相关文章

PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
oracle11.2g递归查询（树形结构查询）

oracle11.2g递归查询（树形结构查询）

转自： 一 二 简单语法介绍 一、树型表结构：节点ID 上级ID 节点名称二、公式： select 节点ID,节点名称,levelfrom 表connect by prior 节点ID=上级节点IDstart with 上级节点ID=节点值 oracle官网解说 开发人员：SQL 递归： 在 Oracle Database 11g 第 2 版中查询层次结构数据的快速
阅读更多...
Leetcode面试经典150题-128.最长连续序列-递归版本另解

Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的，但是可能代码比较复杂，这回来个简洁版的，这个是递归版本 可以看看之前的版本，两个版本面试用哪个都保过 解法都在代码里，不懂就留言或者私信 class Solution {/**对于之前的解法，我现在提供一共更优的解，但是这种可能会比较难懂一些（思想方面）代码其实是很简洁的，总体思想如下：不需要排序直接把所有数放入map，map的key是当前数字，value是当前数开始的
阅读更多...
【UVA】10651-Pebble Solitaire（直接递归或者记忆化）

【UVA】10651-Pebble Solitaire（直接递归或者记忆化）

不知道这个题UVA的数据是怎么的，用2个方法交了，第一次直接递归，第二次记忆化剪枝，时间竟然一样！？ 直接郁闷了，简单的二进制表示状态和二进制运算。 14145176 10651 Pebble Solitaire Accepted C++ 0.009 2014-09-04 09:18:21 #include<cstdio>#include<algorithm>#inclu
阅读更多...
笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机（二)二叉树非递归前序遍历

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机（二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机（二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用，那个马的关系，后面就注意，dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ
阅读更多...
HCIA--实验十：路由的递归特性

HCIA--实验十：路由的递归特性

递归路由的理解 一、实验内容 1.需求/要求： 使用4台路由器，在AR1和AR4上分别配置一个LOOPBACK接口，根据路由的递归特性，写一系列的静态路由实现让1.1.1.1和4.4.4.4的双向通信。 二、实验过程 1.拓扑图： 2.步骤： （下列命令行可以直接复制在ensp） 1.如拓扑图所示，配置各路由器的基本信息： 各接口的ip地址及子网掩码，给AR1和AR4分别配置
阅读更多...
Winform中在窗体中的Paint事件中重绘会导致递归问题？

Winform中在窗体中的Paint事件中重绘会导致递归问题？

在 WinForms 应用程序中，如果在窗体的 Paint 事件处理程序中不断调用 Invalidate 方法，确实可能会导致递归调用的问题。这是因为每次调用 Invalidate 方法时，都会向消息队列添加一个绘制消息，当消息队列中的绘制消息被处理时，会触发 Paint 事件。如果 Paint 事件处理程序中又调用了 Invalidate，就会形成一个循环，导致递归调用 Paint 事件，这
阅读更多...
每日OJ_牛客_求和（递归深搜）

每日OJ_牛客_求和（递归深搜）

目录 牛客_求和（递归深搜） 解析代码 牛客_求和（递归深搜） 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数，如果累加和大于等于目标，结束递归。此时如果累加和正好等于目标，则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程，找到所有的组合。 #include <iostream>#include <cmath>#in
阅读更多...
归并排序-非递归实现

归并排序-非递归实现

归并排序的非递归实现  我们可以把 一个数组 先拆分成 最小单元，这是分， 拆分成最小单元之后，我们对每个最小单元进行一次合并，这是治 最小单元 合并一次之后，我们继续 在上一次合并的基础上拆分，并且合并这是 合 ， 直到 整个数组 只被拆成了两部分，在进行最终一次的和   我们画图举个例子 源代码如下，我们的merge的合并函数的参数是  原数组，左侧小数组索引位置开头，左侧小数
阅读更多...
力扣 | 递归 | 区间上的动态规划 | 486. 预测赢家

力扣 | 递归 | 区间上的动态规划 | 486. 预测赢家

文章目录 一、递归二、区间动态规划 LeetCode：486. 预测赢家 一、递归 注意到本题数据范围为 1 < = n < = 20 1<=n<=20 1<=n<=20，因此可以使用递归枚举选择方式，时间复杂度为 2 20 = 1024 ∗ 1024 = 1048576 = 1.05 × 1 0 6 2^{20} = 1024*1024=1048576=1.05 × 10^
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2