递归思想

在此之前，我们先来聊聊递归的思想
递归是计算的基本思想之一，想象一下，你是一个老师，要解释什么是“递归”，你可能会说：“递归就是我给你们举的例子，这个例子就是递归的一个实例。” 这就是递归的本质：用递归自身来解释递归

递归的工作原理

递归的工作原理可以想象成俄罗斯套娃，每个娃娃里面都有一个更小的娃娃，直到最小的那个。在编程中，这就像是函数A调用自己A，函数A又调用自己A，如此继续，直到达到最小的娃娃（也就是递归的基本情况），然后开始一层层解开，直到回到最初的那个函数A
再换一个例子，想象一下，你正在爬楼梯，每爬一阶，你就离顶层更近一步。递归也是这样，每次函数调用自己时，都会更接近基本情况（base case），也就是递归结束的条件

递归的两个关键部分

1.基本情况（Base Case）：这是递归停止的条件，就像最小的俄罗斯套娃，没有更小的娃娃了。或则说，类似于你爬到顶层，就不再爬了在编程中，这通常是最简单的问题，可以直接解决，不需要进一步递归
递推关系（Recursive Case）：这是函数如何调用自己的部分，每次调用都应该让问题更接近基本情况

具体实例

1.阶乘是一个数所有正整数的乘积。例如，5的阶乘（5!）是5×4×3×2×1=120

以下是C语言的代码：

#include <stdio.h>

// 阶乘函数
unsigned long long factorial(unsigned int n) {
    if (n == 0 || n == 1) {  // 基本情况：如果n为0或1，直接返回1
        return 1;
    } else {  // 递推关系：否则返回n乘以(n-1)的阶乘
        return n * factorial(n - 1);
    }
}

int main() {
    unsigned int num = 5;
    printf("%u 的阶乘是 %llu\n", num, factorial(num));
    return 0;
}

2.斐波那契数列

斐波那契数列是这样的数列：0, 1, 1, 2, 3, 5, 8, 13, …，其中每个数是前两个数的和。

以下是C语言代码：

#include <stdio.h>

// 斐波那契函数
int fibonacci(int n) {
    if (n == 0) {  // 基本情况：如果n为0，返回0
        return 0;
    } else if (n == 1) {  // 基本情况：如果n为1，返回1
        return 1;
    } else {  // 递推关系：否则返回前两个斐波那契数的和
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int num = 6;
    printf("斐波那契数列的第 %d 项是 %d\n", num, fibonacci(num));
    return 0;
}

总结

递归在编程中是一种强大的编程技术，它通过函数自我调用来解决问题。在使用递归时，确保有明确的基本情况和递推关系，这样可以避免无限递归和栈溢出的问题。希望这些例子能帮助你理解递归的概念和应用

二叉树的遍历

通过上面的例子你应该大致理解了递归的思想了，那么接下来我们回到本次要讲的正题————二叉树的遍历。相信学数据结构的同学对它一定不陌生！二叉树的遍历是按照某种规则，依次访问二叉树中的每个节点，每个节点只访问一次。主要有三种遍历方式：先序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）和后序遍历（Postorder Traversal）

先序遍历（Preorder Traversal）

定义：先访问根节点，然后遍历左子树，最后遍历右子树。
递归算法：访问根节点，然后对左子树和右子树递归执行先序遍历。
非递归算法：使用栈来模拟递归过程。首先将根节点入栈，然后循环执行以下步骤：弹出栈顶节点，访问它，然后将它的右子节点和左子节点依次入栈（注意顺序，先右后左）

假设我们有如下的二叉树：

对于先序遍历，简单来说就是指按照“根节点 -> 左子树 -> 右子树”的顺序访问二叉树的每个节点,以下是递归算法的实现

void preOrderTraversal(TreeNode* root) {
    if (root == NULL) return; // 基本情况：如果节点为空，返回
    printf("%d ", root->val); // 访问根节点
    preOrderTraversal(root->left); // 递归遍历左子树
    preOrderTraversal(root->right); // 递归遍历右子树
}

这段代码首先检查根节点是否为空，如果为空则返回。如果不为空，它打印根节点的值，然后递归地遍历左子树和右子树
遍历下来的结果就是：1, 2, 4, 5, 3

接下来是非递归的遍历算法的实现

void preOrderTraversalIterative(TreeNode* root) {
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        if (node != NULL) {
            printf("%d ", node->val); // 访问节点
            s.push(node->right); // 先右后左，保持顺序
            s.push(node->left);
        }
    }
}

这段代码使用一个栈来模拟递归过程。它首先将根节点压入栈中，然后循环直到栈为空。在每次循环中，它弹出栈顶节点，访问它，然后将右子节点和左子节点依次压入栈中，所以遍历下来的结果就是：非递归遍历结果：1, 2, 4, 5, 3

中序遍历

定义：先遍历左子树，然后访问根节点，最后遍历右子树
递归算法：对左子树递归执行中序遍历，访问根节点，然后对右子树递归执行中序遍历
非递归算法：使用栈来模拟递归过程。从根节点开始，将节点依次入栈直到到达最左节点，然后访问它并转向右子节点，重复此过程

还是上述的二叉树为例子

对与中序遍历便是指按照“左子树 -> 根节点 -> 右子树”的顺序访问二叉树的每个节点，以下是递归算法得的实现

void inOrderTraversal(TreeNode* root) {
    if (root == NULL) return; // 基本情况：如果节点为空，返回
    inOrderTraversal(root->left); // 递归遍历左子树
    printf("%d ", root->val); // 访问根节点
    inOrderTraversal(root->right); // 递归遍历右子树
}

这段代码首先检查根节点是否为空，如果为空则返回。如果不为空，它递归地遍历左子树，打印根节点的值，然后递归地遍历右子树,所以遍历的结果便是：4, 2, 5, 1, 3

接下来是非递归算法的实现

void inOrderTraversalIterative(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* current = root;
    while (current != NULL || !s.empty()) {
        while (current != NULL) {
            s.push(current);
            current = current->left;
        }
        current = s.top();
        s.pop();
        printf("%d ", current->val); // 访问节点
        current = current->right;
    }
}

这段代码使用一个栈来模拟递归过程。它首先将当前节点及其所有左子节点压入栈中，直到当前节点为空。然后，它弹出栈顶节点，访问它，并转向其右子节点,所以遍历出来的结果便是：4, 2, 5, 1, 3

后序遍历

定义：先遍历左子树，然后遍历右子树，最后访问根节点
递归算法：对左子树和右子树递归执行后序遍历，然后访问根节点
非递归算法：使用两个栈来模拟递归过程。第一个栈用于遍历，第二个栈用于反转遍历顺序。将根节点入第一个栈，然后循环执行以下步骤：从第一个栈中弹出节点并将其入第二个栈，然后将其子节点依次入第一个栈（注意顺序，先右后左）。当第一个栈为空时，从第二个栈中弹出节点并访问它们

二叉树例子同上

对于后序遍历便是指按照“左子树 -> 右子树 -> 根节点”的顺序访问二叉树的每个节点，接下来是递归算法的实现

void postOrderTraversal(TreeNode* root) {
    if (root == NULL) return; // 基本情况：如果节点为空，返回
    postOrderTraversal(root->left); // 递归遍历左子树
    postOrderTraversal(root->right); // 递归遍历右子树
    printf("%d ", root->val); // 访问根节点
}

这段代码首先检查根节点是否为空，如果为空则返回。如果不为空，它递归地遍历左子树和右子树，然后打印根节点的值，所以遍历出来的结果是：4, 5, 2, 6, 7, 3, 1

接下来是非递归算法的实现

void postOrderTraversalIterative(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* prev = NULL;
    TreeNode* current = root;
    while (current != NULL || !s.empty()) {
        while (current != NULL) {
            s.push(current);
            current = current->left;
        }
        current = s.top();
        if (current->right == NULL || current->right == prev) {
            printf("%d ", current->val); // 访问节点
            s.pop();
            prev = current;
            current = NULL;
        } else {
            current = current->right;
        }
    }
}

这段代码使用一个栈来模拟递归过程。它首先将当前节点及其所有左子节点压入栈中，直到当前节点为空。然后，它检查栈顶节点的右子节点是否为空或者是否已经访问过。如果是，它弹出栈顶节点，访问它，并更新prev节点。否则，它转向栈顶节点的右子节点,所以运行出来的结果便是：4, 5, 2, 6, 7, 3, 1

总结

递归方法：直观，易于实现，但可能遇到栈溢出的问题
非递归方法：使用栈或队列来模拟递归过程，可以避免栈溢出的问题，但实现相对复杂

写在最后

朋友们，学习编程可能会在一开始感到有些挑战，但请记住，每个编程高手都是从基础开始，一步一个脚印走过来的。递归是编程中一个非常强大的工具，一旦你掌握了它，很多复杂的问题都会变得简单起来。记住，每个人的学习速度都是不同的，不要和别人比较，而是和昨天的自己比较。只要你们保持耐心和热情，不断练习，很快就能掌握递归的。加油，你们可以做到的！😉