尾递归与尾调用

在很多的高级语言中，都会提到尾递归的特性。

当年在大学里学递归时，老师特别强调递归次数与进程栈的关系。

递归越多，函数入栈越多，由于进程有栈空间有线，会生成栈越界。

下图是一个入栈的过程。

main call funcA ;

funcA call funcB

当然了，递归引发栈越界只是调用栈越界的方式之一，如果代码写的调用层级特别多，则也会引发栈越界。

随着语言的发展（我想其中是语言的编译器与解释器的发展），发明一种叫“尾调用”的技术。

来个例子:

function B

{

    do someting;

    return 0;

}

function A

{

   do someting;

    return B;

}

这种A使用return B.把自己的返回与调用B联合在了一起。这就叫尾调用。

解释器就发现，当调用B完成之后，A的栈上的数据不会再被使用。那不如先把A从栈上POP出去。再调用B。

如下来个不是尾调用的例子。

function A1

{

   do someting;

   ret = B();

    return ret;

}

A1在调用了B后，还会使用栈上的内容。或是如下例子也不是尾调用。

function A2

{

   do someting;

      return B()+1;

}

尾调用不一定出现在函数尾部，只要是最后一步操作即可。

如function A3

{

      if(xxx == true) then

           return B(); //这里就是尾调用。

     else

           a++;

     end

}

尾调用的栈是怎么玩的呢？

尾递归正是使用了尾调用的特性。

在写递归函数时，特意使用尾调用的写法。这样递归时，栈空间不会随着递归次数而增长。这样就节约了很多的内存。

PS：我写的文章就很一般了，在网上有很多对尾调用和尾递归的介绍。大家可以多参考一下。

http://www.ruanyifeng.com/blog/2015/04/tail-call.html

C语言的编译器在加上－O2也可以识别并优化尾调用 。

有一例子，请大家自己行参考吧

http://blog.sina.com.cn/s/blog_5374d6e30100t0do.html