尾递归优化的含义

104359176

一直不明白尾递归优化是如何做到的, 今天突然灵光一闪, 好像明白了:

1. 
   
2. call(a,b, call(c, d, call(e,f)))
   

复制代码

1. 
   
2. 
   
3. my $return = call(e,f);
   
4. for (call(c, d), call(a, b)) {
   
5.    my $return = call(c, d, $return)
   
6. }
   
7. 
   

复制代码

这里的调用不是参数调用, 是表达式展开. 每次将计算的结果, 添加到表达式的末尾.
   

sunzhiguolu

大神能否说下, 这个东西用在啥地方?

104359176

尾递归优化的概念是从编译器出来的，
如果是设计语言的就知道，函数的设计会有一个局部的堆栈空间。
如果递归太深的话，这个堆栈就会超出设计容量。采用这种技术，可以用堆空间置换堆栈空间。

这种技术如果用在优化代码上，可以对不支持尾递归优化的语言进行手动优化。提高效率。

Java 就不支持尾递归优化。另外许多语言的函数栈都有容量限制。

zhlong8

你这不对啊。

尾调用（tail call）指的是 一个函数（A）return 语句返回的是一个函数调用（B），那局部变量显然不会再用到了可以直接从栈上删除（引用，closure 什么的由GC负责），B的返回地址可以直接替换为 A 的，这样可以节省A占用的栈空间。

如果 A 里调用的还是 A 或者几个不同函数互相调用，这就叫尾递归，这样优化使栈不会不断增长。

zhlong8

至于具体怎么做设计个简单的只支持一条占用栈的空指令和函数调用的虚拟机就明白了

104359176

zhlong8 发表于 2016-08-29 11:04
你这不对啊。

尾调用（tail call）指的是 一个函数（A）return 语句返回的是一个函数调用（B），那局部 ...

看我的例子就知道，只有表达式最后一个调用是函数本身，才能被优化。

104359176

最简单的一个例子就是 map 的嵌套

1. map { expr } map { expr } map { expr } @array;
   
2. my @return = map { expr  } @array;
   
3. for (1,2) {
   
4.   @return = map { expr } @return;
   
5. }
   
6.    

复制代码

@array[/code]：
可以优化成：

zhlong8

我不明白把返回值替换成中间变量和主题有什么关系