递归转非递归

尾递归优化为循环

1、阶乘的尾递归循环

// 递归版本
int factorial(int n, int acc = 1) {
    if (n == 0) return acc;
    return factorial(n-1, acc * n); // 尾递归
}

// 或者
int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n-1); // 尾递归
}

// 迭代版本
int factorial_iter(int n) {
    int acc = 1;
    for (int i = 1; i <= n; i++) {
        acc *= i;
    }
    return acc;
}

2、斐波那契数列的尾递归循环

// 递归版本
int fibonacci(int n){
    if(n <= 1) return n;
    return fibonacci(n-1) + fibonacci(n-2);  // 尾递归
}

//迭代版本
int fibonacci(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

显式栈模拟递归调用栈

恶补函数帧栈

基础

指针字节与计算机位数

内存中的每一个字节都进行了编号,这个编号就是地址,地址的意义在于我们可以快速读取到这个地址上面的数据,编号越大说明这个字节距离初始字节越远,那么阿Q提问:最远的地址有多大呢?

如果是32位系统,主流计算机是二进制的,那么这个系统的最大寻址能力是2^32,就是32位电脑最多支持4G运存,那么最远的地址就是4G运存的最后一位字节,给这个字节编号就是2^32(一般把这个数用16进制表示),为了能表达这个最大的位置数,就需要想办法了。

一个字节有8个比特位,1个比特位只能表达1和0两个数,2个比特位可以表达4个数,要表达2^32个数,就需要32个比特位,也就是4个字节,所以一个指针变量至少需要4个字节才够用。那为什么不用5个字节6个字节呢,浪费内存资源。 (同理 64位系统 指针则需要8个字节)

获取代码区的地址

映射文件 – 查看函数和代码段的精确布局的gcc指令
// powershell
gcc -o test test.c "-Wl,-Map,test.map"
__builtin_return_address(n)

GCC/Clang 的内建函数,用于获取调用栈中第 n 层函数调用的返回地址

#include <stdio.h>

void f(){
	printf("return address( example_function() ):%p\n",__builtin_return_address(0));  // 返回的为调用者 example_function()中 f()代码块地址
	printf("return return( main() ):%p\n",__builtin_return_address(1));     // 返回的 为 第二层调用者 main()中 example_function()代码块地址
	printf("test return( __mainCRTStartup() ):%p\n",__builtin_return_address(2));     // 返回的为第三层调用者 __mainCRTStartup() 中 main()代码块地址
}

void example_function() {
    printf("This is a function.\n");
	f();
}

int main() {
    example_function();
    example_function();
    return 0;
}
可以看出example_function()和__mainCRTStartup()调用地址未发生改变,而main()调用由于位置改变,其地址发生了改变
访问代码段的内容

可以通过函数指针或直接地址(操作系统将代码段标记为可执行(EXECUTE)和可读(READ),但不可写(WRITE))

#include <stdio.h>
#include <stdint.h>

void example_function() {
    printf("This is a function.\n");
}

int main() {
    // 获取函数地址
    uintptr_t func_addr = (uintptr_t)example_function;  // 用unsigned __int64指针
    printf("函数地址: %p\n", (void*)func_addr);
    
    // 读取前4字节的机器码(x86-64示例)
    unsigned char *code = (unsigned char*)func_addr;
    printf("机器码: %02x %02x %02x %02x\n", code[0], code[1], code[2], code[3]);
    
    return 0;
}

/*
输出结果:
函数地址: 00007FF606D616D0
机器码: 55 48 89 e5
*/

阿Q将两者合在一起看看

#include <stdio.h>
#include <stdint.h>

void f(){
	printf("调用example_function() f()块地址:%p\n",__builtin_return_address(0));  // 返回的为调用者 example_function()中 f()代码块地址
	printf("调用者main() example_function()块地址:%p\n",__builtin_return_address(1));     // 返回的 为 第二层调用者 main()中 example_function()代码块地址
	printf("调用者__mainCRTStartup() main()块地址:%p\n",__builtin_return_address(2));     // 返回的为第三层调用者 __mainCRTStartup() 中 main()代码块地址
}

void example_function() {
    printf("This is a function.\n");
	f();
}

int main() {
	uintptr_t main_addr = (uintptr_t) main;
	printf("main函数地址:%p\n",(void*)main_addr);

	uintptr_t example_function_address = (uintptr_t)example_function;
	printf("example_function函数地址:%p\n",(void*)example_function_address);

	uintptr_t f_address = (uintptr_t)f;
	printf("f函数地址:%p\n\n",(void*)f_address);

	example_function();
    example_function();
    return 0;
}

在看完函数帧栈后这些地址间有什么意思就能明白了。

寄存器 (汇编)

eax – “累加器”, 它是很多加法乘法指令的缺省寄存器。

ebx – “基地址”寄存器。

esi/edi – “源/目标索引寄存器”, ds:esi – 指向源串; es:edi – 指向目标串

ebp – 基址指针

esp – 栈顶指针,在32位平台,esp每次减少4个字节。

// 汇编
push ebp;  // 保存当前ebp
mov ebp, esp; // ebp 设为当前栈底指针
sub esp,xxx;  预留xxx 字节给函数 

函数帧栈

阿Q推荐先看大佬的这篇文章函数栈帧(涉及汇编)。

帧栈

维护函数帧栈的两个寄存器(存的是地址哦)
寄存器 ebp:栈底指针 (高地址)
寄存器 esp:栈顶指针 (低地址)
阿Q特别说明函数的栈区使用是从高地址向低地址的。

阿Q:不同编译环境,不同平台的栈帧操作可能有差异,掌握其思想即可。

阿Q将手绘下面代码如何创建函数栈帧的,具体过程包括汇编方面还得看大佬的文章。

#include <stdio.h>
int Add(int x, int y)
{
	int z = 0;
	z = x + y;
	return z;
}
int main()
{
	int a = 10;
	int b = 20;
	int c = 0;
	c = Add(a, b);
	return 0;
}

压栈过程

调用main之前
进入main
局部变量
函数被调用(进入被调函数前)
进入被调函数

压栈小结

之后的局部变量操作是一样的,整个最终入栈的情况如下:

#include <stdio.h>
int Add(int x, int y)
{
	int z = 0;
	z = x + y;
	return z;
}
int main()
{
	int a = 10;
	int b = 20;
	int c = 0;
	c = Add(a, b);
	return 0;
}

出栈过程

小结

阿Q:整个过程中的 ebp 指针的动态变化太有思想了!

ebp在每次进入新的函数栈域都会首先压入存有原来ebp所在的地址(能保证回退过程中退回到上一层的函数栈域)。

在进入函数前,esp朝低地址前进n个空间(开辟空间),与此时ebp 管理当前函数栈帧。同时给当前函数空间附初值。进入函数后碰到局部变量,则在函数空间中修改某处 如 ebp-8 的值(保存局部变量)。如果该函数调用了某个函数F,则ebp就需要维护F的栈底。(同样首先压入当前ebp所在的地址,ebp再进行移动)

调用函数时(在进入被调函数之前),栈中压入有以下内容(*):

1、值传递时,压入实参的值,而非地址(即:传入形参);指针传递或者引用传递,则压入的是实参的地址。 (从入栈角度考虑)

2、调用函数下一条指令的地址 (从出栈角度考虑)

3、当前的ebp的地址 (从出栈角度考虑)

以上均为阿Q自己的思考,若有问题,请大佬们指出。

显式栈模拟方法

阿Q下面直接使用stack库。

函数帧栈思想

阿Q建议不要用软件去真的模拟系统函数栈(虽然这是通用方法),模拟过程的压栈和出栈性能还不如递归过程。

主要是函数栈的思想,对不同的算法题作针对性的模拟即可。

如:二叉树遍历的非递归算法

二叉树遍历非递归算法中,阿Q为什么将结点压栈和出栈就能实现非递归算法呢?

看小结(*)部分,根结点满足这些内容嘛?

1、结点存有左右子树,可以压入左右子树的地址。 (指针传递)

2、结点出栈后,函数就接着运行下一条指令(即:不需要压入下一条指令的地址)。

3、结点出栈后,ebp返回到上一个ebp(当前结点 – 当前ebp -> 双亲结点 – 上一个ebp的地址),满足。

void inorderTraversal(Btree root) {
    std::stack<BtNode*> stk;
    Btree curr = root;
    while (curr || !stk.empty()) {
        // 模拟递归左子树
        while (curr) {
            stk.push(curr);
            curr = curr->lchild;
        }
        // 处理当前节点
        curr = stk.top();
        stk.pop();
        std::cout << curr->data << " ";
        // 转向右子树(这一步无需加条件的 - 中序遍历)
        curr = curr->rchild;
    }
}

通用转换类型

1、定义帧结构

递归的每一步调用会保存当前参数、局部变量和执行位置。需要将这些信息封装成一个结构体(或类),作为栈帧(Stack Frame)存入显式栈中。

struct StackFrame {
    int n;          // 递归参数(例如阶乘的n)
    int result;     // 局部变量(例如当前计算结果)
    int stage;      // 执行阶段(标记当前执行到递归的哪一步)
    // 其他必要的参数和局部变量...
};

2、初始化栈

初始参数入栈,模拟递归的第一次调用

stack<StackFrame> stk;
stk.push({n, 0, 0}); // 初始化参数为n,stage标记为0(起始阶段)

3、循环处理栈帧

通过循环逐步处理栈顶帧,模拟递归的展开和回溯。

while (!stk.empty()) {
    StackFrame& frame = stk.top(); // 获取当前栈顶帧,引用可以修改原有地址内的值
    switch (frame.stage) {
        case 0: // 阶段0:处理递归的第一步操作
            if (递归终止条件) {
                // 直接计算并保存结果,模拟递归返回
                frame.result = ...;
                stk.pop();
                
                // 若需要返回结果,则将结果传回
                stk.top().result = frame.result;
            } else {
                // 标记当前执行阶段(例如即将处理子问题)
                frame.stage = 1;
                // 压入子问题(模拟递归调用)
                stk.push({子问题参数, 0, 0});
            }
            break;
        case 1: // 阶段1:处理子问题返回后的操作
            // 使用子问题的结果(frame.result或其他子帧结果)
            frame.result = ...;
            stk.pop(); // 当前帧处理完毕
            
            //  若需要返回结果, 将结果传回
            stk.top().result = frame.result;
            break;
        // 更多阶段(复杂递归需要多个阶段)
    }
}

4、处理多阶段递归

若递归中存在多个子调用(如二叉树遍历中的左、右子树),需通过 stage 标记区分处理顺序。

case 0: // 处理左子树前
    frame.stage = 1;
    stk.push({left_child, ...});
    break;
case 1: // 左子树返回后处理当前节点
    process_current_node();
    frame.stage = 2;
    stk.push({right_child, ...});
    break;
case 2: // 右子树返回后收尾
    stk.pop();
    break;

实例操作

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

显示栈实现

// 栈帧中有:当前值、当前返回的结果、问题状态
struct StackFrame {
    int n;
    int result;
    int stage; // 0:未处理子问题, 1:子问题已返回
};

int factorial_iter(int n) {
    std::stack<StackFrame> stk;
    stk.push({n, 0, 0}); // 初始帧
    int final_result = 0;

    while (!stk.empty()) {
        StackFrame& frame = stk.top();
        switch (frame.stage) {
            case 0:
                if (frame.n == 1) {
                    // 终止条件,返回1
                    frame.result = 1;
                    stk.pop();
                    if (stk.empty()) final_result = frame.result;

                    // 将结果传回
                    else stk.top().result = frame.result;

                } else {
                    // 标记阶段1,压入子问题 n-1
                    frame.stage = 1;
                    stk.push({frame.n - 1, 0, 0});
                }
                break;
            case 1:
                // 子问题已返回,计算当前结果
                frame.result = frame.n * stk.top().result;
                stk.pop();

                if (stk.empty()) {
                    final_result = frame.result;
                }

                // 将结果传回
                else stk.top().result = frame.result; 

                break;
        }
    }
    return final_result;
}

阿Q:能否用该方法实现二叉树的前、中、后序遍历?

在DeepSeek-R1的帮助下,阿Q兴奋的晚上睡不着觉,连夜赶完这部分内容。

#include <iostream>
#include <stack>

typedef char TElemtype;

struct TreeNode {
    TElemtype val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}   // 这种创建树的方法太叼了!
};

// 栈帧有:树结点、当前经过结点的阶段,由于Traverse函数不返回值,因此不需要存 返回值。
struct StackFrame
{
    /* data */
    std::pair<TreeNode*,int> NodeState; // template<class T1, class T2> Struct pair
    // 0 - 第一次经过;  1 - 第二次经过; 2 - 第三次经过
};

void operate(TreeNode* Node)
{
    std::cout << Node->val << "  ";
}

enum TraversalType {PREODER, INORDER, POSTORDER};

// 重点
void Traversal(TreeNode* root,TraversalType type=PREODER) {
    // 使用栈保存节点及其处理阶段
    std::stack<StackFrame> stk;
    stk.push({{root,0}}); // 初始压入根节点,阶段0

    while (!stk.empty()) {
        auto& [node, stage] = stk.top().NodeState;
        if (!node) {
            stk.pop(); // 弹出空节点
            continue;
        }

        switch (stage) {
            case 0:
                // 阶段0:处理左子树
                if(type == PREODER) operate(node);
                stk.top().NodeState.second = 1; // 标记为阶段1
                if (node->left) {
                    stk.push({{node->left, 0}}); // 压入左子节点
                }
                break;
            case 1:
                // 阶段1:访问当前节点
                // 操作
                if(type == INORDER) operate(node);
                stk.top().NodeState.second = 2; // 标记为阶段2
                if (node->right) {
                    stk.push({{node->right, 0}}); // 压入右子节点
                }
                break;
            case 2:
                // 阶段2:完成,弹出节点
                // 终止条件
                if(type == POSTORDER) operate(node);
                stk.pop();
                break;
        }
    }
}

int main() {
    // 示例树:1(2(4,5),3)
    TreeNode* root = new TreeNode('A');
    root->left = new TreeNode('B');
    root->right = new TreeNode('C');
    root->left->left = new TreeNode('D');
    root->left->right = new TreeNode('E');

    std::cout << "PreOrder: ";
    Traversal(root,PREODER); // 输出:ABDEC
    std::cout << std::endl;

    std::cout << " InOrder: ";
    Traversal(root,INORDER); // 输出:DBEAC
    std::cout << std::endl;

    std::cout << "PostOrder: ";
    Traversal(root,POSTORDER); // 输出:DEBCA
    std::cout << std::endl;

    return 0;
}

/*
输出结果:
PreOrder: A  B  D  E  C  
InOrder: D  B  E  A  C
PostOrder: D  E  B  C  A
*/
该方法清晰实现了路径(唯一),在第1次经过就访问 – 前序; 第二次经过 – 中序; 第三次经过 – 后序。

总结

对于尾递归,一般就不用显示栈了,太麻烦。

对于非递归模拟栈中结点压入栈就能包含以下内容的情况:1、传参;2、返回下一条指令地址;3、结点自带地址,容易维护ebp,建议使用函数栈帧的思想,而不是用软件真的模拟函数栈帧。

对于递归转非递归不容易做到的情况,使用显示模拟栈,此方法虽然可能减少了内存占用,但是栈操作可能比递归略慢。(看使用场景)

评论

发送评论 编辑评论


				
上一篇
下一篇