浅谈尾调用和尾递归（C语言）

淡淡的烟草味﹌ 2022-06-02 07:17 245阅读 0赞

# 什么是尾调用 #

在计算机科学里，尾调用是指一个函数里的最后一个动作是一个函数调用的情形，即这个调用的返回值直接被当前函数返回的情形。这种情形下称该调用位置称为“尾位置”。

说得通俗点，尾调用就是指某个函数的最后一步是调用另一个函数。这个调用位置称为“尾位置”。

比如有个函数叫`fun`，其实现是：

int fun(void)
    {
        foo();
    }

上面代码中，函数`fun`的最后一步是调用函数`foo`，这就叫尾调用。

以下三种情况，哪种属于尾调用？

// 情况一
    int fun(void)
    {
        int a = foo();
        return a;
    }
    
    // 情况二
    int g(void)
    {
        return 3+foo();
    }
    
    // 情况三
    int s(int x) 
    {
      if (x > 0)
        return m(x);
    
      return r(x);
    }

情况一是调用函数`foo`之后，还有别的操作，所以不属于尾调用，即使语义一样。

情况二在调用后也有别的操作，所以不属于尾调用，即使写在同一行。

情况三中，不管x取什么值，最后一步操作都是函数调用，所以属于尾调用。

# 尾调用优化 #

函数调用会在栈上形成一个”栈帧”（frame stack），用来保存函数参数、返回地址、局部变量等信息。如果函数A调用函数B，那么在A的栈帧下方（假设栈从高地址向低地址生长），还会形成B的栈帧。等到B函数返回，B的栈帧才会消失。如果函数B又调用了函数C，那么B的栈帧下方又形成C的栈帧。以此类推，所有的栈帧堆叠起来，就形成了一个”调用栈”（call stack）。如下图所示：

![这里写图片描述][SouthEast]

由于尾调用是外层函数的最后一步操作，尾调用返回后，外层函数也就返回了。执行尾调用的时候，外层函数栈帧中保存的调用位置、内部变量等信息都不会再用到了，所以，可以用内层函数（即尾调用函数）的栈帧覆盖外层函数的栈帧（而不是在外层函数栈帧下面再新开一个），这样可以节省栈空间。这就叫做”尾调用优化”（Tail call optimization）.

如果你觉得抽象，可以举个例子：

int f(void)
    {
      int m = 1;
      int n = 2;
      return g(m + n);
    }

对于以上代码，`f();`等同于`g(3);`调用`g(3)`之后，函数`f()`就结束了。所以执行到`g(3)`的时候，完全可以用`g(3)`的栈帧覆盖`f()`的栈帧。

# 尾递归 #

若一个函数在尾位置调用自身，则称这种情况为尾递归。尾递归是递归的一种特殊情形。

# 尾递归优化 #

当编译器检测到尾递归的时候，它就覆盖当前的栈帧而不是在栈中去创建一个新的。无论调用多少次，只要每次都将栈空间覆盖（或重用），其空间占用就是一个常数，即`O(1)`.所以，尾递归优化使原本`O(n)`的调用栈空间只需要`O(1)`.

# 递归和尾递归的比较 #

我们以求阶乘为例，比较一下递归和尾递归的不同。

## 递归写法 ##

int factorial(int n) 
    {
        if(n < 0)
            return 0;  //参数错误则返回0
        else if (n == 0 || n == 1)
            return 1;
        else
            return n * fact(n - 1);
    }

假设计算`factorial(5)`,那么栈空间的变化如下：

factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2))) 5 * (4 * (3 * (2 * factorial(1)))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120

可观察，栈从左到右，增加到一个峰值，然后从右到左缩小。

## 尾递归写法 ##

int factorial_tail(int n, int product_from_n)
    {
        if (n < 0)
            return 0; //参数错误则返回0
        else if (n == 0)
            return 1;
        else if (n == 1)
            return product_from_n;
        else
            return factorial_tail(n - 1, n * product_from_n);
    
    }

初次接触这种写法一定会觉得很别扭，求`n!`为什么要传入2个参数呢？先不着急回答，我们先模拟计算机算一遍。

如果求`n!`，则需要传入参数n和1（为什么？后文会说明）.所以`5！=factorial_tail(5,1);`  
计算过程如下：

factorial_tail(5,1)
    factorial_tail(4,5*1) = factorial_tail(4,5)
    factorial_tail(3,4*5*1) = factorial_tail(3,20)
    factorial_tail(2,3*4*5*1) = factorial_tail(2,60)
    factorial_tail(1,2*3*4*5*1) = factorial_tail(1,120)
    120

`factorial_tail(x,y)`这个函数的作用是求((x!)\*y).  
显而易见，当x==1时，结果就是y,所以有

else if (n == 1)
        return product_from_n;

当x!=1的时候，将`(x!)*y`恒等变形，变为`(x-1)!*(x*y)`,所以调用`factorial_tail(x,y)`就变成了调用`factorial_tail(x-1,x*y)`

于是有代码中的

return factorial_tail(n - 1, n * product_from_n);

欲求n的阶乘，当然要使y=1，所以，`5！=factorial_tail(5,1);`

不难看出，这种思路的本质是：将单次计算的结果缓存起来，作为参数传递给下一次调用，每一次调用都离最终结果近了一步，相当于是迭代。

本来还想从汇编代码的角度分析一下尾递归优化，囿于篇幅，只能下次谈了。

参考资料  
\[1\][https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8][https_zh.wikipedia.org_wiki_E5_B0_BE_E8_B0_83_E7_94_A8]  
\[2\][http://www.voidcn.com/article/p-qdsabmbw-xk.html][http_www.voidcn.com_article_p-qdsabmbw-xk.html]  
\[3\][http://www.ruanyifeng.com/blog/2015/04/tail-call.html][http_www.ruanyifeng.com_blog_2015_04_tail-call.html]

[SouthEast]: /images/20220602/42fa6788fec64c698edd4b4be004ecc9.png
[https_zh.wikipedia.org_wiki_E5_B0_BE_E8_B0_83_E7_94_A8]: https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8
[http_www.voidcn.com_article_p-qdsabmbw-xk.html]: http://www.voidcn.com/article/p-qdsabmbw-xk.html
[http_www.ruanyifeng.com_blog_2015_04_tail-call.html]: http://www.ruanyifeng.com/blog/2015/04/tail-call.html