插曲:关于递归

1 概述

循环与递归是算法中最常见的控制过程的方法,循环自不必说,只要学过计算机语言,必然都会讲这种控制结构;而对于递归,大家也能写得很漂亮(树算法中和图算法中使用递归的场景也特别多)。

递归的好处也显而易见,代码体积小,容易维护。然而,递归并不是万能钥匙,特别是当运行环境内存空间有限以及要求高性能的场景。下文首先介绍递归的运行原理,然后用实例说明递归的代价,接着讲解递归如何转换成循环及其限制,最后对本文进行总结。

2 递归的运行原理

这里的递归特指递归函数,递归函数在程序中执行的原理是什么(冯诺伊曼体系下)?这是认识递归函数执行效率的关键。下面我们以构建斐波那契数列为例,说明递归函数的执行过程。构建斐波那契数列的递归函数(golang实现)如下:

fun Fib(n int) int{     
   ret : = 0     
   if n == 0 || n == 1 {    // 1 
       ret = 1     // 2                   
   }     
   ret = Fib(n - 1) + Fib(n - 2)  // 3     
   return ret 
 }

学过编译原理的童鞋都知道,函数是在栈(对,就是童鞋们在数据结构上学习的栈)上运行的,如果n=4,Fib(4)的原理示意如图1所示:

图1:fib(4)动态示意图

要求fib(4),必须在栈上求Fib(3)(要求Fib(3),必须再为在栈上求Fib(2)和Fib(1),要求Fib(2),在栈上继续求fib(1)和Fib(0))和Fib(2)(类似fib(3)的过程)。这样的递归算法,必须在栈上记录函内的局部变量、传递参数、返回地址(直到调用结束后回到哪)和上一栈帧的EBP和BP(恢复调用者栈),并且频繁出栈入栈是需要系统开销的,虽然单次入栈出栈开销不大,但是如果要求Fib(1000)这样的函数,恐怕一般的单机估计得跑几十分钟甚至半天了(在笔者的mac本上跑了几分钟都没出来,直接把进程杀了,不能忍)。

为了有个直观的感受,笔者特意做了一个简单的试验(见我的git),分别以递归和非递归求解Fib(10), Fib(20), Fib(30), Fib(40), Fib(50)的运行结果,如下图所示:

图2:递归和非递归试验结果


从运行结果可以看出,当n值较小时(<10)时,递归运行的时间少于非递归运行时间(原因应该是非递归分配slice需要占用相对较长的时间,这种写法有些弱智,其实只需要两个中间变量即可,类似于不用第三个变量实现两变量值交换的思路),当n>=20后,非递归运行时间远低于递归运行时间,n越大,非递归相对递归越高效。

当然,非递归高效运行也不是没有代价的,相比递归函数,编写代码的难度要更高并且更难维护。

3 递归转非递归

那如何将递归函数转换为非递归函数呢?是否所有的递归函数都能换成非递归函数?

首先必须弄清楚递归有哪些种类,递归有两种,一种是单向递归,类似于Fib(n)的这种是一种典型的单向递归(Fib(n)->Fib(n-1)->Fib(n-2)->…->Fib(1));另一种的递归(不妨称其为交互递归,不一定准确)的形式为:F1(n) -> F2(n) -> F1(n-1) -> F2(n-1) -> …

单向递归中,以尾递归效率最高,尾递归是指以调用自身结尾的函数。上文中提到的Fib(n)就不是尾递归,但是可以转换为递归函数如下(不防比较一下尾递归写法和非递归写法的效率):

fun TailFib(n, f1, f2 int) int{
    if n < 2{
        return f1
    }
    return TailFib(n-1, f2, f1 + f2)
}

其对应的非递归写法为:

func NotRecursion(n, f1, f2 int) int{
    if n < 2{
        return 1;
    }
    i := 0
    for i <= n {
        f2 = f1 + f2
        f1 = f2 - f1
    }
    return f1
}

尾递归在递归函数中的效率最高,因为当递归调用返回时,返回到上一层递归调用语句的下一语句,而这个位置正好是程序的结尾,因此递归工作栈中可以不保存返回地址;除了返回值和引用值外,其他参数和局部变量都不再需要。根据尾递归的逻辑,很容易写出非递归的算法。

对于交互递归,其形式相对较为复杂,可能在作具体项目时,无意中就写出来了。交互递归相对单向递归而言,难以直接写出相应的非递归函数,需要抽取出F1(n) -> F2(n) -> F1(n-1) -> F2(n-1) -> …里面的F1(i)->F2(i)->F1(i-1)->F2(i-1)这里面的公共逻辑,即用一个迭代可以表述其中的转换。如果难以抽取,最直接的办法是模拟入栈出栈过程,抽取里面的参数特征,建立循环迭代(后续想到了补一个例子)。

4 总结

递归是算法中特别是树、图等结构中常用的方法,理解递归的运行原理是写出高效代码的关键。针对效率要求比较高的场景,可以尝试写出非递归的版本。总体上而言,递归写法的代码体积小、易维护,非递归写法代码理解维护稍显困难,但执行效率相对较高。

About author

虞双齐,全栈开发工程师,Google SRE实践者。提供Golang开发、技术实践与架构等咨询服务。

动态分享到微博@虞双齐,代码存放在 Github,博文分享在 个人博客上。