9

通用的递归转循环方法

 3 years ago
source link: https://zhuanlan.zhihu.com/p/136511316
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

通用的递归转循环方法

字节前端内推加V, bramblesX

今天中午群里面刚好讨论起一些算法怎么用非递归写，就想起来以前写过伪递归转成循环的通用方法，并且在文章里面说过，所有的递归都能等效成一个栈+循环，那么今天干脆就把通用的方法在这里给大家讲讲。

我们以树的递归遍历作为例子，来讲如何用通用的方法将递归函数转换成栈+循环。递归的例子如下，大家不如先思考一下怎么做：

interface TreeNode {
    content: number,
    children?: TreeNode[],
}

function travel(node: TreeNode): number {
    console.log(node.content);
    let i = 0;
    let sum = node.content;
    while (node.children && i < node.children.length) {
        sum += travel(node.children[i]);
        i++;
    }
    return sum;
}

为什么递归能等效于栈+循环

学习方法之前我们先探讨一下为什么递归能够等效于栈+循环，其实确切地说函数的调用就已经能等效成栈+循环了，而递归只是其中的一种而已。

这要从函数是如何被调用的讲起，如《尾递归为啥能优化？》里面有讲过基本的函数调用过程和函数栈的作用跟功能，但还不足以解释完整的过程，我们还需要一点点更底层的知识。

假设如下图，我们做了一个简化的模型，左边是内存里面程序的机器码，右边上部分是寄存器，右边下部分是一块内存作为我们的函数栈。我们把寄存器简化成 4 个，PC 寄存器是保存我们下一个指令会执行的位置，R0、R1 和 R2 三个为通用寄存器，并且我们约定 R0 用来储存函数返回的结果。（下面每一处的表动我们都会用红色标记）

假设上图就是我们的初始情况，开始执行。

（上图）开始调用 funcA ，funcA 的地址是 0x0051 （0x0050只是占个位不用理他），将当前 PC 里的值压入栈中（这就是函数之后需要返回的地址），然后再把 PC 寄存器的值修改指向 0x0051 （调用的函数地址）。

（上图）现在开始执行 funcA 的代码，将 R0 置成 1，我们约定了用 R0 用做 return 的值，所以在 return 后返回的值会从 R0 里面取。

（上图）执行 funcA 的 return，将 PC 置成栈顶的值 0x005A （函数要返回的位置），并将 0x005A 出栈（不需要用了）。因为 PC 保存的是程序下一步执行的位置，那么下一步就会返回到之前调用 funcA 的位置并接着执行。

（上图）现在我们回到了 main 函数里的 0x005A 接着执行，因为我们之前约定了用 R0 作为函数返回的数据，我们先用 R1 把 R0 存起来，避免调用 funcB 的时候把 R0 覆盖掉。

（上图）接下来调用 funcB 也是相同的过程就不一一赘述了，funcB 返回 2。

（上图）最后，main 函数剩下的代码执行完毕，返回到 main 函数调用的位置 0x00FF，并且 R0 作为返回值是 3 。

所以 CPU 就可以看成是一个循环，不断从 PC 指向的位置去执行代，在函数调用的过程中用 PC 去改变接下来要去执行的位置，用栈来跟踪找到调用完一个函数再回来的路，避免迷路。

如果用 js 代码解释的话就是如下这样：

let pc: number = 0; // pc 寄存器，用来标记程序下一个指令执行的位置
let r0: number = 0; // r0 寄存器，用来储存函数返回的值
let stack: number[] = [];

const code: Command[];

function run(address: number) {
    const command = code[address];
    if (command.isCall) { // 如果是调用函数
        stack.push(pc); // 用栈记录回来的位置
        pc = command.callAddress; // 设置 pc 让 cpu 去执行调用的函数
    }
    if (command.isReturn) { // 当函数返回的时候
        pc = stack.pop(); // 出栈之前在函数调用时记录的返回位置，并设置 pc 让 cpu 执行回到的位置
    }
    // other...
}

while (true) { // cpu 执行指令的循环
    run(pc); 
    pc++; // pc 自增自动执行下一条指令
}

既然 cpu 调用函数相当于一个 while(true) 循环，来实现我们函数的执行和调用过程？答案自然是完全可以！只要自己接管整个函数调用的过程，完全可以实现将函数调用全部转换成 while(true)。当然，递归也不例外，前置知识已经讲完了，正式开始将递归转换成循环

照猫画虎转换递归

接下来就开始一步一步将下面我们的示例代码转换成递归。

interface TreeNode {
    content: number,
    children?: TreeNode[],
}

function travel(node: TreeNode): number {
    console.log(node.content);
    let i = 0;
    let sum = node.content;
    while (node.children && i < node.children.length) {
        sum += travel(node.children[i]);
        i++;
    }
    return sum;
}

首先先搭一个架子，就像上面的模拟 cpu 调用函数代码一样，有栈 $stack、函数返回用的寄存器 $result ，以及调用函数的 $call 函数和用于函数返回的 $return 函数。并且我们补充了压入栈里面的参数和栈上面声明的变量。

咦是不是发现我们缺了一个很重要的东西 PC？没错，在 JS 里面除了我们重写解释器，否则怎么样也没办法做到像 CPU 那样一个指令一个指令地执行。但是我们转念一想，是不是 cpu 在执行绝大部分指令的时候，pc 都是自增 1 的，相当于我们根本没动它，只有需要把跳转的逻辑代码打断，然后手动控制跳转不就行了吗？

答案正是如此，控制程序下一步往哪里跑的技术叫做 Continuation。

interface TravelStack {
    continuation: number;

    node: TreeNode;

    i: number;
    sum: number;
}

function travel2(node: TreeNode) {

    const $stack: TravelStack[] = [];
    let $result: number = 0;

    const $call = (node: TreeNode) => $stack.push({
        continuation: 0, // 控制程序下一步往哪里跑，返回往哪里返回
        
        // 下面是调用函数的参数， 函数的参数是什么抄下来就行
        node: node,
       
        // 函数栈上面生命的变量，函数里面声明了什么变量都要抄下来
        i: 0,
        sum: 0,
    });

    const $return = (n: number) => {
        $stack.pop();
        $result = n;
    };

    $call(node);
    
    while(true) {
    }
}

框架已经打好了，我们看看逻辑代码哪里需要拆分，原则上调用递归函数的位置，包括包着调用递归函数的 if else / for / while 等快都需要拆分，这里以 while 循环为例：

function travel(node: TreeNode): number {
    console.log(node.content);
    let i = 0;
    let sum = node.content;

    // 循环需要拆分
    while (node.children && i < node.children.length) {
        sum += /* 调用递归的位置需要拆分 */ travel(node.children[i]);
        i++;
    }
   // 需要拆分
    return sum;
}

用 swtich / case 来将逻辑代码拆分成一片一片，用 continuation 来手动控制代码执行的顺序：

const current = $stack[$stack.length - 1]; // 拿到我们当前的栈
const { continuation, node } = top; // 从我们指定的位置执行

switch (continuation) {

    case 0: {
        console.log(node.content);
        current.i = 0; // 变量全都生命到栈上空间里（栈帧）
        current.sum = node.content;

        current.continuation = 1; break; // 跳转到接下来的循环代码
    }

    case 1: {
        if (node.children && top.i < node.children.length) {
            $call(node.children[top.i]) // 调用递归函数，子节点作为参数
            current.continuation = 2; break; // 记录调用返回后的继续执行的位置
        }

        top.continuation = 3; break; // 循环结束，跳到 3
    }

    case 2: {
        top.sum += $result; // 从 $result 寄存器拿到函数调用的结果
        top.i++;
        top.continuation = 1; break; // 循环还没结束，继续回到循环的头部
    }

    case 3: {
        $return(top.sum); break; // 函数返回
    }
}

至此我们已经将一个递归函数转换成了循环函数，最后我们看一下完整的代码：

// test.ts
interface TreeNode {
    content: number,
    children?: TreeNode[],
}

const root: TreeNode = {
    content: 1,
    children: [
        {
            content: 2,
            children: [
                { content: 3 },
                { content: 4 }
            ]
        },
        {
            content: 5,
            children: [
                { content: 6 },
                {
                    content: 7,
                    children: [
                        { content: 8 }, { content: 9 }
                    ]
                }
            ]
        }
    ]
};

function travel(node: TreeNode): number {
    console.log(node.content);
    let i = 0;
    let sum = node.content;
    while (node.children && i < node.children.length) {
        sum += travel(node.children[i]);
        i++;
    }
    return sum;
}

interface TravelStack {
    continuation: number;

    node: TreeNode;

    i: number;
    sum: number;
}

function travel2(node: TreeNode) {

    const $stack: TravelStack[] = [];
    let $result: number = 0;

    const $call = (node: TreeNode) => $stack.push({
        continuation: 0,

        node: node,

        i: 0,
        sum: 0,
    });

    const $return = (n: number) => {
        $stack.pop();
        $result = n;
    };

    $call(node);

    while ($stack.length > 0) {
        const current = $stack[$stack.length - 1];
        const { continuation, node } = current;

        switch (continuation) {

            case 0: {
                console.log(node.content);
                current.i = 0;
                current.sum = node.content;

                current.continuation = 1; break;
            }

            case 1: {
                if (node.children && current.i < node.children.length) {
                    $call(node.children[current.i])
                    current.continuation = 2; break;
                }

                current.continuation = 3; break;
            }

            case 2: {
                current.sum += $result;
                current.i++;
                current.continuation = 1; break;
            }

            case 3: {
                $return(current.sum); break;
            }

        }
    }

    return $result;
}

console.log('travel', travel(root));
console.log('travel2', travel2(root));

执行结果如下：

好了文章写完了，不知道大家有没有觉得这种技术很神奇，但是也很陌生呢？其实并不是的，如果大家看过 babel 翻译过后的 async 函数一定已有很强的既视感，用类似这种 switch / case 截断代码手动控制 Continuation 的技术是实现协程的常规手段。比如 c 的一些轻量级携程库，也是这么实现的。

不过你要说我写了那么多，到底有啥用？嗯……放心，搬业务砖肯定用不上，我也没用上过，但是不妨碍我觉得好玩。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK