在《数据结构与算法分析:C描述》(Data Structures and Algorithm Analysis In C)的第三章中,以打印链表为例,提到了尾递归(tail recursion)并指出了尾递归是使用递归极其不当的例子,它指出虽然编译器会对尾递归自动优化,但即便如此最好还是不要去写尾递归。而我在《算法精解:C语言描述》(Mastering
Algorithms with C)中也看到书中提到编译器会对尾递归进行优化,但是此书貌似看起来很提倡使用。
这里对于不了解尾递归为何物的童鞋们,我想探讨几个基本问题。
【1】什么是尾递归?
【2】编译器是怎样优化尾递归的?
【3】优化工作交给编译器还是交给自己?
第一个问题,什么是尾递归?
直接上代码:
这两个函数都是在计算n的阶乘,结果一样的,但只有下面的facttail函数才是尾递归。
所以可以看出,尾递归的概念就是函数返回之前的最后一个操作若是递归调用,则该函数进行了尾递归,而上面的fact函数,最后一个操作是乘法,所以显然不是尾递归。
第二个问题,编译器是怎样优化尾递归的?
我们知道递归调用是通过栈来实现的,每调用一次函数,系统都将函数当前的变量、返回地址等信息保存为一个栈帧压入到栈中,那么一旦要处理的运算很大或者数据很多,有可能会导致很多函数调用或者很大的栈帧,这样不断的压栈,很容易导致栈的溢出。
我们回过头看一下尾递归的特性,函数在递归调用之前已经把所有的计算任务已经完毕了,他只要把得到的结果全交给子函数就可以了,无需保存什么,子函数其实可以不需要再去创建一个栈帧,直接把就着当前栈帧,把原先的数据覆盖即可。相对的,如果是普通的递归,函数在递归调用之前并没有完成全部计算,还需要调用递归函数完成后才能完成运算任务,比如return
n * fact(n - 1);这句话,这个fact(n)在算完fact(n-1)之后才能得到n * fact(n - 1)的运算结果然后才能返回。
综上所述,编译器对尾递归的优化实际上就是当他发现你丫在做尾递归的时候,就不会去不断创建新的栈帧,而是就着当前的栈帧不断的去覆盖,一来防止栈溢出,二来节省了调用函数时创建栈帧的开销,用《算法精解》里面的原话就是:“When a compiler detects a call that is tail recursive,
it overwrites the current activation record instead of pushing a new one onto the stack.”
第三个问题,优化工作交给编译器还是交给自己?
这个怎么说呢,据网上查阅,java,C#和python都不支持编译环境自动优化尾递归,这种情况下,当然是别用递归效率最高,可以看下这里http://www.cnblogs.com/Alexander-Lee/archive/2010/09/16/1827587.html。但是对于C语言来说,编译器白提供的服务,用了也不差,毕竟递归代码会好理解一点,但换句话说,如果写到尾递归这份上了,变成非递归已经很好实现了,完全可以用循环来搞定,所以呢,这个时候,就看个人喜好了。
注:
老赵 大神也写过一篇关于尾递归的文章,不过是用C#描述的,我没怎么看,感兴趣可以了解下。http://www.cnblogs.com/JeffreyZhao/archive/2009/03/26/tail-recursion-and-continuation.html
分享到:
相关推荐
浅谈 递归机制 非递归 转换 txt
/*int f(int n,int a1,int a2) { if(n) return a1; else return f(n - 1, a2, a1 + a2); }*/
这几天看到几篇关于尾递归的文章,之前对尾递归没有多大概念,所以回头研究了一下尾递归。 尾递归的概念尾递归(Tail Recursion)的概念是递归概念的一个子集。对于普通的递归,由于必须要记住递归的调用堆栈,...
本文实例讲述了JS尾递归的实现方法及代码优化技巧。分享给大家供大家参考,具体如下: 在学习数据结构和算法的时候,我们都知道所有的递归都是可以优化成栈+循环的。 对于特定的递归函数,一般我们都是手动对它们...
本文实例讲述了es6函数之尾递归用法。分享给大家供大家参考,具体如下: 函数调用自身,称为递归,如果尾调用自身,就称为尾递归。 递归非常耗费内存。因为需要同时保存成千上百个调用帧,很容易发生“栈溢出”错误...
本篇文章主要介绍了python使用递归、尾递归、循环三种方式实现斐波那契数列,非常具有实用价值,需要的朋友可以参考下
尾递归简介 尾递归是函数返回最后一个操作是递归调用,则该函数是尾递归。 递归是线性的比如factorial函数每一次调用都会创建一个新的栈(last-in-first-out)通过不断的压栈,来创建递归, 很容易导致栈的溢出。而尾...
浅谈C语言函数的递归调用.pdf
在C语言的环境下,运用尾递归将整数转换为二进制数 在C语言的环境下,运用尾递归将整数转换为二进制数
尾递归与Continuation递归与尾递归关于递归操作,相信大家都已经不陌生。简单地说,一个函数直接或间接地调用自身,是为直接或间接递归。例如,我们可以使用递归来计算一个单向链表的长度: 代码如下:public class ...
主要介绍了C#中的尾递归与Continuation详解,本文讲解了递归与尾递归、尾递归与Continuation、Continuation的改进等内容,需要的朋友可以参考下
本文实例讲述了Python递归及尾递归优化操作。分享给大家供大家参考,具体如下: 1、递归介绍 递归简而言之就是自己调用自己。使用递归解决问题的核心就是分析出递归的模型,看这个问题能拆分出和自己类似的问题并且...
普通递归和尾递归如果仅仅只是从代码的角度出发来看,我们可能发现不了他的特点,所以笔者利用两张堆栈上的图来展示具体的差距在哪,首先我们来看看普通的递归调用的情况,如下图1.1所示: 假设这里执行的函数是...
浅谈C语言函数的递归调用 (1)
浅谈T-SQL语言之递归查询.pdf
这是一个关于尾递归和Cooper变换的文档,有兴趣的人可以下载。
fibonacci数列的各种解法,递归、存储优化的递归、自下而上的递归(迭代法)、尾递归。其中分析内容请移步我的博客、
简单叙述递归算法在java编程中的应用,使用递归的利弊。
主要介绍了浅谈Python 递归算法指归,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧