递归与迭代：编程中的两种重要控制结构

创作时间:

作者:

@小白创作中心

递归与迭代：编程中的两种重要控制结构

引用

CSDN

https://m.blog.csdn.net/weixin_45885074/article/details/138050075

递归和迭代是编程中两个非常重要的概念，它们在数据处理和算法实现中扮演着关键角色。本文将通过对比分析和具体示例，帮助读者深入理解这两个概念及其应用场景。

递归与迭代的基本概念

迭代（Iteration）

迭代是一种常见的循环控制结构，通过重复执行一段代码来处理数据。在迭代过程中，程序从数据结构的起始位置开始遍历，直到达到终点。迭代适用于处理线性数据结构，如数组和链表。

递归（Recursion）

递归则是一种通过函数自我调用来解决问题的方法。递归过程可以分为两个阶段：前向遍历和回溯。前向遍历类似于迭代，从数据结构的起始位置向终点移动；回溯阶段则从终点返回到起点。递归特别适用于处理嵌套或层次结构的数据，如树和图。

递归与迭代的应用对比

示例一：链表节点高度赋值

假设有一个包含N个节点的链表，每个节点都有一个height变量。目标是让链表末尾的节点height为0，倒数第二个节点height为1，依此类推，直到头部节点height为N-1。其中N是一个未知数。

迭代方法：

需要先遍历链表获取N的值
再次遍历链表为每个节点赋值
总共需要遍历两次链表

递归方法：

递归到链表末尾
在回溯过程中依次为节点赋值
只需遍历一次链表

以下是递归实现的代码示例：

#include <iostream>
#define N 9
using namespace std;

struct Node {
    int height;
    Node* next;
};

Node* GetLinklist() {
    Node* root = nullptr;
    Node* mid = nullptr;
    for(int i = 0; i < N; i++) {
        Node* temp = new Node;
        if(i == 0) {
            root = temp;
            mid = temp;
        } else {
            mid->next = temp;
            mid = temp;
        }
    }
    mid->next = nullptr;
    return root;
}

void AssignData(Node* node) {
    static int cnt = 0;
    if(node == nullptr) return;
    AssignData(node->next);
    node->height = cnt;
    cnt++;
}

int main() {
    Node* root = GetLinklist();
    AssignData(root);
    return 0;
}

示例二：计算二叉树的高度

计算二叉树的高度需要递归地获取左右子树的高度，然后取最大值加1。这是一个典型的递归应用场景。

以下是计算二叉树高度的递归代码：

struct Node {
    int data;
    Node* right;
    Node* left;
};

int get_height(Node* node) {
    if(node == nullptr) return 0;
    return max(get_height(node->left), get_height(node->right)) + 1;
}

int main() {
    Node* root = nullptr; // 假设root是一个多层树的根
    get_height(root);
    return 0;
}