递归(Recursive)函数是在运行的过程又会直接或间接地调用自己本身的函数。通常透过递归函数可以快速地验证我们的算法,用简短的代码处理复杂的问题,但是函数在调用时需要创建新的堆栈框(Stack Frame),除了会需要额外的开支(Overhead)之外,如果在函数中调用函数,而这函数又会调用函数,持续下去,很容易就会造成堆栈溢出(Stack Overflow)。虽然有些编程语言的编译器会做尾端调用消除(Tail Call Elimination, TCE)的优化(Tail Call Optimization, TCO),可以让我们将递归函数设计成尾端递归(Tail Recursive)来避免分配额外的堆栈空间创建新的堆栈框,但编译器其实并不能都保证一定会去进行尾端调用消除。遇到这种情形,我们还是只好使用迭代函数。那么大问题就来了:要如何将递归函数改成迭代函数呢?

将递归函数改成迭代函数的流程

以下会以经典的费氏数列来说明将递归函数逐步改成迭代函数的流程。

费氏数列又称费布那西(Fibonacci)数列,它是一种发散数列,第 1 项的值为 0,第 2 项的值为 1,第 #{{n}}# 项(#{{ n \geq 3 }}#)的值为第 #{{n - 1}}# 项和第 #{{n - 2}}# 项的总和。费氏数列看起来会长得像以下这样:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

以数学函数来表示费氏数列,可以写成:

#{{{
\begin{alignedat}{2}
F(1) &{}={}&& 0 \\
F(2) &{}={}&& 1 \\
F(n) &{}={}&& F(n - 1) + F(n - 2), \text{where } n \geq 3 \\
\end{alignedat}
}}}#

有没有清楚发现费氏数列函数在运算的时候又去调用自己本身的函数?所以它是一个递归函数。

步骤一:理解递归函数

要将递归函数改为迭代函数,我们要先理解这个函数的每个部份(或是至少递归调用的部份)在干嘛。费氏数列很简单,就不多说了。如果用代码来实作费氏数列,最直觉的方式会是以下这个样子:

由于写程序习惯从 0 开始数,所以这边将费氏数列的第一项设计为 #{{ F(0) }}#。

步骤二:将递归函数改为尾端递归

函数被递归调用的位置若是在函数运行的最后,就是尾端递归。以上代码因为费氏数列函数在被递归调用后还多做了加法运算,所以不能算是尾端递归。我们要想办法将它改成尾端递归,好让我们能够把它变成迭代函数。

我们可以增加递归函数的参数,让函数在递归的时候带走更多信息。像是费氏数列,就可以让递归函数多加两个参数,来保存每次递归时第 #{{ n - 1 }}# 项的值和第 #{{ n }}# 项的值。如此一来就可以在每次递归时计算出下一项的值,并将这个值又作为下一次递归调用时的第 #{{ n }}# 项的值,同时也将原本第 #{{ n }}# 项的值作为下一次第 #{{ n - 1 }}# 项的值。而原本的参数 n 就会变成计次用途了。

修改后的代码如下:

步骤三:用循环将递归函数的主体(Body)包起来

这是一个过渡性的步骤(代码不一定能编译成功),我们要用一个总是可以被运行的循环来将原本递归函数主体中的所有程序叙述包起来,并在循环中的最后加上 break 关键字来跳离循环。

所以上面的代码要修改成:

步骤四:将尾端递归调用的程序叙述改为直接修改函数参数的叙述,并加上 continue 关键字

这也是一个过渡性的步骤(代码不一定能编译成功),如果尾端递归调用的地方有需要回传(return)尾端递归调用后的结果的话,就直接把那个「return」拿掉吧!

修改后的代码如下:

步骤五:整理代码

将以上被我们改到变得怪怪的代码稍微整理一下,让它可以被正确编译。

至此我们就成功地把递归的费氏数列函数改成迭代版本了!

更多的转换例子

简单的递归函数基本上都可以尝试使用上面的流程来转换成迭代函数,以下再举几个例子。

阶乘(Factorial)函数

计算某数(正整数)的阶乘,是指计算所有小于及等于该数的正整数的积。方程式表示如下:

#{{{
n! = 1 \times 2 \times 3 \times \dotsb \times (n - 1) \times n
}}}#

且定义

#{{{
0! = 1
}}}#

我们可以将阶乘的第 #{{ n }}# 项移出,使得 #{{n! = n \times (n - 1)!}}#。如何?明显又是个递归函数了吧!

由于阶乘函数比费氏数列函数还要简单,所以直接看以下代码吧!

二元搜索(Binary Search)

二元搜索法是一种搜索算法,可以在已排序好的数组中快速搜索指定的元素。有关于二元搜索法的介绍可以参考这篇文章:

二元搜索法可以用递归函数来实作,也可以转成迭代函数,代码如下:

二元搜索树(BST, Binary Search Tree)的搜索

二元搜索树是一种二元树(Binary Tree)。节点如果有左边子节点的话,其左边子节点连接的所有值都必须要小于该节点的值;节点如果有右边子节点的话,其右边子节点连接的所有值都必须要大于或等于该节点的值。例如以下结构即为二元搜索树:

        7
       / \
      /   \
     /     \
    /       \
   3         9
  / \       / \
 /   \     /   \
1     5   8     9
 \   / \
  2 4   6

若我们想在二元搜索树中找出拥有某个目标值的节点,或者小于但最接近这个目标值的节点,可以使用递归函数来轻易完成。代码如下:

同样地,若要把这个递归函数改成迭代函数,就要让它使用尾端递归。我们可以替这个递归函数添加一个参数来保存当 node 参数为空时,函数会回传的结果。

函数修改后如下:

按照先前介绍的方式,把只有尾端递归调用的递归函数改成迭代的版本吧!

递归关系式(Recurrence Relation)的另外转换方式

对于阶乘数列或是费氏数列这类有递归关系的数列,我们其实不一定要找出其尾端递归函数,就有办法将其转成迭代函数。

就以前面非尾端递归版本的阶乘递归函数来举例好了。代码如下:

步骤一:将递归调用的部份拆成子进程

为了方便理解代码,我们要先从递归调用发生的位置,一直到之后函数结束运行的部份都转成一个子进程(另外写成新的函数)。

代码如下:

步骤二:拆解子进程的程序叙述

将子进程的步骤分为三大部份:递归调用(取得前项结果)、计算目前这项的结果,以及回传结果。

代码如下:

步骤三:替子进程添加参数,使其可以透过参数传入前项结果

以往我们在求递归关系式之数列的时候,为了要求得第 #{{n}}# 项的结果,就要先去计算第 #{{n}}# 项之前的结果。但是我们现在要反过来,变成先求得第 #{{n}}# 项之前的结果,再直接用这个结果算出第 #{{n}}# 项。有没有听起来更像是用循环就可以完成的事?

这个步骤算是一个过渡性的步骤(单独看无意义),是为了之后的修改而做的铺垫。

步骤四:让子进程除了回传目前这项的计算结果外,也回传计算下一项时会用到的参数

若我们让子进程除了回传目前这项的计算结果外,也回传计算下一项时会用到的参数,就可以在每次调用子进程后,得到目前这项的结果,以及计算下一项需要用到的参数,如此一来我们便可以再利用这些数值套入公式,直接计算出下一项的结果。当然,如果有不变的参数,子进程就没有必要再将其回传出来了。这也是一个过渡性的步骤(单独看无意义,且回传出来的新参数暂时用不到)。

步骤五:现在,改用循环来调用子进程吧!

我们只要按照递归关系数列的基础项定义参数的初始值,就可以从初始值利用循环重复调用刚才完成的子进程,来计算到我们要的第 #{{n}}# 项。

以阶乘数列来说,基础项就是 #{{0! = 1}}#,所以计算时要从 #{{1!}}# 开始计算。#{{1!}}# 的前一项是 #{{0!}}#,也就是要以 #{{1}}# 作为子进程上一项的结果,并以计算第 1 项为始去调用子进程,计算 #{{n}}# 次后就是我们要的第 #{{n}}# 项了。程序修改如下:

步骤六:整理代码

观察我们目前写出来的代码,其实不难发现,因为一开始就有给子进程计算目前这项数值时会用到的前项数值,所以子进程完全不会进入递归调用的流程,所以这部份的代码可以直接拿掉了。再来就是递归关系数列的基础项,原先有用 if 等关键字事先判断,也可以视情况将其移除。

于是我们可以将代码整理如下:

至此我们就成功地把递归的阶乘函数改成迭代版本了!

步骤七:将子进程内联(inline)回原本的函数

如果子进程并不复杂,我们完全可以考虑把它移回原来的函数中,省下调用函数时所产生的开支。虽然有些编译器会自动对简单的函数做内联优化,但这件事自己来做才能保证最终它们不是分开的函数。

步骤八:再次整理代码

内联之后的迭代函数,可能会有一些冗余的地方可以进行合并与删减。

整理一下后,代码最终会变成:

更多的转换例子

有递归关系的数列函数基本上都可以尝试使用上面的流程来转换成迭代函数,以下再举别的例子。

费氏数列

本篇文章最一开始就有详细说明费氏数列的递归函数转迭代函数的方式,现在则要改用第二种方式来进行转换。

直接看以下代码吧!

动态规划

动态规划是一个将递归函数转迭代函数的有效方式,不过有点复杂,请参考另一篇文章:

自行创建空间来模拟堆栈空间

实务上,我们常会遇到无法或是很难被转成尾端递归的递归函数,这时候我们可以自行创建额外的堆栈(Stack)空间或堆积(Heap)空间来模拟函数在递归时使用到的堆栈空间,以此提升性能或是避免堆栈空间不足。换句话说,我们要自己写程序实作出递归发生时,参数(和区域变量,但不建议)在模拟的堆栈空间内的访问情形。

要以这样的方式将递归函数转成迭代函数,可以先根据递归函数主体的结构来判断能不能符合以下几种型样(pattern),再分别用不同的方式来模拟堆栈空间的访问。

递归函数无回传,递归调用只连续发生在尾端
void f(param1, param2, ..., paramN) {
    // do something

    f(a, b, ..., n); // recursive call 1
    f(aa, bb, ..., nn); // recursive call 2
    // ...
    f(aaa, bbb, ..., nnn); // recursive call n
}

以上这种递归函数的结构是最简单的,我们只需要先用总是可以被运行的循环来将原本递归函数主体中的所有程序叙述包起来,然后在这个循环外的上方创建一个堆栈空间,把传进递归函数的参数 push 到堆栈空间中(只需存会有变化的参数)。接着在刚才加上的循环内,一开始的时候去 pop 这些参数,用这些参数去做原本该做的事,最后反转(因为堆栈是先进后出)递归调用的部份,并且将递归调用的程序叙述都改成把递归调用时的参数 push 到堆栈空间中。若循环一开始无法从堆栈空间中 pop 到参数,就跳出循环。

所以之后形成的迭代函数看起来会像以下这样:

void f(param1, param2, ..., paramN) {
    stack = Empty Stack;
    push param1, param2, ..., paramN to stack

    loop {
       pop param1, param2, ..., paramN from stack, if pop nothing then break

       // do something

       push aaa, bbb, ..., nnn to stack // recursive call n
       // ...
       push aa, bb, ..., nn to stack // recursive call 2
       push a, b, ..., n to stack // recursive call 1
    }
}

这边要注意的是,递归调用时传入函数的参数有可能会是内容可变的(mutable)指针或是参考,此时就要注意数据改变的地方是否会去影响到其它的递归调用,如果会的话就要用不同的方式来实作了。尾端连续发生的递归调用可以允许夹杂是否要进行递归调用的判断式。

快速排序法的实作方式就是这个型样的典型例子。有关于快速排序法的介绍以及代码,可以参考这篇文章:

递归函数无回传,递归调用只发生在前端
void f(param1, param2, ..., paramN) {
    if condition {
        f(a, b, ..., n); // recursive call
    }

    // do something
}

以上这种递归函数的结构也是最简单的。我们可以先将函数主体分成两个部份,第一个部份就是一开始发生的递归调用(包括是否要进行递归调用的条件式),第二个部份就是递归调用完后续的部份。使第一部份自成一个循环,第二部份自成一个循环。在两个循环的最上方,创建出一个堆栈空间。创建了堆栈空间后,把传进递归函数的参数 push 到堆栈空间中(只需存会变化的参数)。

在第一部份的循环内,将递归调用的程序叙述改成把递归调用时的参数 push 到堆栈空间中,并直接修改参数。若递归调用的条件式无法成立,就跳出循环。

而在第二部份的循环内,一开始要先去 pop 堆栈空间中的参数,并用这些参数去做原本该做的事。若循环一开始无法从堆栈空间中 pop 到参数,就跳出循环。

所以之后形成的迭代函数看起来会像以下这样:

void f(param1, param2, ..., paramN) {
    stack = Empty Stack;
    push param1, param2, ..., paramN to stack

    loop {
        if condition {
            push a, b, ..., n to stack // recursive call
            param1 = a, param2 = b, ..., paramN = n
        } else {
            break;
        }
    }

    loop {
       pop param1, param2, ..., paramN from stack, if pop nothing then break

       // do something
    }
}
递归函数无回传,递归调用只连续发生在前端
void f(param1, param2, ..., paramN) {
    f(a, b, ..., n); // recursive call 1
    f(aa, bb, ..., nn); // recursive call 2
    // ...
    f(aaa, bbb, ..., nnn); // recursive call n

    // do something
}

我们可以先将函数主体分成两个部份,第一个部份就是一开始连续发生的递归调用,第二个部份就是递归调用完后续的部份。使第一部份自成一个循环,第二部份自成一个循环。在两个循环的最上方,创建出两个堆栈空间。第一个堆栈空间要用来存放递归调用时,传进函数的参数(只需存会变化的参数)。第二个堆栈空间则是要存放从第一个堆栈空间中取出来的参数(只需存第二部份会用到的参数)。创建了两个堆栈空间后,把传进递归函数的参数 push 到第一个堆栈空间中。

在第一部份的循环内,一开始要先去 pop 第一个堆栈空间中的这些参数,接着将递归调用的程序叙述都改成把递归调用时的参数 push 到堆栈空间中,最后再把参数 push 进第二个堆栈空间内。若循环一开始无法从第一个堆栈空间中 pop 到参数,就跳出循环。

而在第二部份的循环内,一开始要先去 pop 第二个堆栈空间中的参数,并用这些参数去做原本该做的事。若循环一开始无法从第二个堆栈空间中 pop 到参数,就跳出循环。

所以之后形成的迭代函数看起来会像以下这样:

void f(param1, param2, ..., paramN) {
    stack1 = Empty Stack;
    stack2 = Empty Stack;
    push param1, param2, ..., paramN to stack1

    loop {
        pop param1, param2, ..., paramN from stack1, if pop nothing then break

        push a, b, ..., n to stack1 // recursive call 1
        push aa, bb, ..., nn to stack1 // recursive call 2
        // ...
        push aaa, bbb, ..., nnn to stack1 // recursive call n


        push param1, param2, ..., paramN to stack2
    }

    loop {
       pop param1, param2, ..., paramN from stack2, if pop nothing then break

       // do something
    }
}

这边要注意的是,递归调用时传入函数的参数有可能会是内容可变的指针或是参考,此时就要注意数据改变的地方是否会去影响到其它的递归调用,如果会的话就要用不同的方式来实作了。前端连续发生的递归调用可以允许夹杂是否要进行递归调用的判断式。

不过我们其实比较不希望看到用两个以上的堆栈空间来模拟递归的方式,若还有优化余地,尽量还是将递归函数以一个堆栈空间来实作成迭代函数吧!

递归函数无回传,递归调用只发生在前端和尾端
void f(param1, param2, ..., paramN) {
    if condition1 {
        f(a, b, ..., n); // recursive call 1
    }

    // do something

    if condition2 {
        f(aa, bb, ..., nn); // recursive call 2
    }
}

基本上看到尾端递归的部份,我们都可以用前面提过的方式先将它转成迭代版本。转换后看起来会像以下这样:

void f(param1, param2, ..., paramN) {
    loop {
        if condition1 {
            f(a, b, ..., n); // recursive call 1
        }

        // do something

        if condition2 {
            param1 = aa, param2 = bb, ..., paramN = nn // recursive call 2
            continue;
        }

        break;
    }
}

再来就只剩下前端的递归调用了,虽然它现在出现在一层循环中,我们还是可以套用前面提过的方式来创建堆栈和添加循环。转换后看起来会像以下这样:

void f(param1, param2, ..., paramN) {
    stack = Empty Stack;

    'outer: loop {
        push param1, param2, ..., paramN to stack

        loop {
            if condition1 {
                push a, b, ..., n to stack // recursive call 1
                param1 = a, param2 = b, ..., paramN = n
            } else {
                break;
            }
        }

        loop {
            pop param1, param2, ..., paramN from stack, if pop nothing then break 'outer

            // do something

            if condition2 {
                param1 = aa, param2 = bb, ..., paramN = nn // recursive call 2
                continue 'outer;
            }
        }
    }
}

比较需要注意的是,第二部份的循环中如果堆栈空间已清空的话,是直接跳出外层的循环。且第二部份的循环中,因移除尾端递归而添加的 continue 关键字,其作用对象也是外层循环。原先因移除尾端递归而添加的循环,其中最后使用的 break 关键字就要移除掉,因为现在是依我们自己创建的堆栈空间来决定要不要继续下一次的迭代。

其它

若递归函数的主体无法符合上述提到的型样,可以多加理解该递归函数运作的原理,来进行迭代函数的转换。

例如前面提到的二元搜索树,我们可以用以下的递归函数,来将二元搜索树的数据结构,转成已排序好的数组。

观察这个递归函数的行为,可以了解到它一开始会使用空的数组,接着从二元树最左边的子节点开始将值放进数组中。左边子节点处理完之后就换右边子节点,然后以右边子节点为起始点寻找其下最左边的子节点,如此循环。以下面这个二元搜索树为例:

        7
       / \
      /   \
     /     \
    /       \
   3         9
  / \       / \
 /   \     /   \
1     5   8     9
 \   / \
  2 4   6

从 7 开始找最左边的子节点,找到 1。将 1 放入数组后,再看右边的子节点 2,2 没有子节点,将 2 放入数组。再回到 3 这个节点,将 3 放入数组后,再看右边的子节点 5。从 5 开始找最左边的子节点,找到 4,将 4 放入数组。之后的步骤依此类推。

现在不要理会递归函数怎么实作的,我们就使用一个堆栈空间,来创造出全新的迭代函数吧!

利用堆栈保存往左搜索时遇到的节点,当已经最左时,就将找到的节点值放进数组中,并且再从右边子节点开始找最左边的节点,同样地利用堆栈保存过程中遇到的子节点。而堆栈存在的目的是要记录待处理的节点。于是我们就可以井然有序地实作出以下迭代版本的函数: