关于尾递归的使用详解

这几天看到几篇关于尾递归的文章，之前对尾递归没有多大概念，所以回头研究了一下尾递归。

尾递归的概念
尾递归（Tail Recursion）的概念是递归概念的一个子集。对于普通的递归，由于必须要记住递归的调用堆栈，由此产生的耗用是难以估量的。比如下文中php小节第一个例子使用php写一个阶乘函数，就是由于递归造成了栈溢出的错误。尾递归出现的目的就是消除递归栈耗损这个缺憾的。

从代码层面看，尾递归其实一句话就可以说清楚了：

函数的最后一个操作是递归调用

比如"菲波纳锲"数列的php的递归实现：


代码如下:

fibonacci.php                                                                                                                         
<?php
function fibonacci($n) {
    if ($n < 2) {
        return $n; 
    }   
    return fibonacci($n - 1) + fibonacci($n - 2); 
}

var_dump(fibonacci(30));

这是递归函数，但不是尾递归，因为fibonacci的最后一个操作是加法操作。

转化为尾递归：


代码如下:

function fibonacci2($n, $acc1, $acc2) {
    if ($n == 0) {
        return $acc1;
    }   
    return fibonacci2($n-1, $acc2, $acc1 + $acc2);
}

fibonacci2就是一个尾递归，它增加两个累加器acc1和acc2，并给出初始的值。记住：递归转化为尾递归的思想一定是增加累加器，减少递归外操作。
尾递归在不同语言上的应用也是不同的。最常使用的就是函数式编程Erlang，几乎是所有出现递归的函数全部都修改成为尾递归。下面说一下尾递归在几个不同的语言上的表现和应用。

php中的尾递归
我们做个实验

普通递归：


代码如下:

<?php
function factorial($n)
{
    if($n == 0) {
        return 1;
    }   
    return factorial($n-1) * $n; 
}

var_dump(factorial(100000000));

尾递归：


代码如下:

<?php
function factorial($n, $acc)
{
    if($n == 0) {
        return $acc;
    } 
    return factorial($n-1, $acc * $n);
}

var_dump(factorial(100000000, 1));

实验结果：

事实证明，
尾递归在php中是没有任何优化效果的!

C中的尾递归

在C中的尾递归优化是gcc编译器做的。在gcc编译的时候加上-O2会对尾递归进行优化

我们可以直接看生成的汇编代码：

(使用gdb， gcc –O2 factorial.c –o factorial;    disass factorial)

未加-O2生成的汇编：

加了O2优化的汇编：

不要头大，我也是初看汇编，但是这份代码非常简单，去网上稍微搜搜命令，大致就能理解：


代码如下:

function factoral(n, sum) {
    while(n != 0){
        sum = n * sum
        n = n-1
    }
    return sum

}

gcc做的确实是智能优化。

如果你还有兴趣，你可以使用-O3对尾递归进行优化，并查看其中的汇编指令

-O3的优化是直接将循环展开

总结

一般的线性递归修改成为尾递归最大的优势在于减少了递归调用栈的开销。从php那个例子就明显看出来递归开销对程序的影响。但是并不是所有语言都支持尾递归的，即使支持尾递归的语言也一般是在编译阶段对尾递归进行优化，比如上例中的C语言对尾递归的优化。在使用尾递归对代码进行优化的时候，必须先了解这门语言对尾递归的支持。

赞 (0)

相关推荐

  • 讲解Python中的递归函数

    在函数内部,可以调用其他函数.如果一个函数在内部调用自身本身,这个函数就是递归函数. 举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示,可以看出: fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n 所以,fact(n)可以表示为n x fact(n-1),只有n=1时需要特殊处理. 于是,fact(n)用递归的方式写出来就是: def fact(n):

  • 尾递归详细总结分析

    尾递归详细总结分析

    一. 尾递归与Continuation 递归与尾递归关于递归操作,相信大家都已经不陌生.简单地说,一个函数直接或间接地调用自身,是为直接或间接递归.例如,我们可以使用递归来计算一个单向链表的长度: 复制代码 代码如下: public class Node{    public Node(int value, Node next)    {        this.Value = value;        this.Next = next;    } public int Value { get

  • python实现斐波那契递归函数的方法

    本文以一个简单的实例讲述了python实现斐波那契数列数列递归函数的方法,代码精简易懂.分享给大家供大家参考之用. 主要函数代码如下: def fab(n): if n==1: return 1 if n==0: return 0 else: result=int(fab(n-1))+int(fab(n-2)) return result 测试代码如下: for i in range(10): print fab(i) 希望本文所述对大家Python程序设计的学习有所帮助.

  • Lua中的函数（function）、可变参数、局部函数、尾递归优化等实例讲解

    一.函数 在Lua中,函数是作为"第一类值"(First-Class Value),这表示函数可以存储在变量中,可以通过参数传递给其他函数,或者作为函数的返回值(类比C/C++中的函数指针),这种特性使Lua具有极大的灵活性.   Lua对函数式编程提供了良好的支持,可以支持嵌套函数.   另外,Lua既可以调用Lua编写的函数,还可以调用C语言编写的函数(Lua所有的标准库都是C语言写的).   定义一个函数 复制代码 代码如下: function hello() print('he

  • 使用python实现递归版汉诺塔示例(汉诺塔递归算法)

    利用python实现的汉诺塔.带有图形演示 复制代码 代码如下: from time import sleep def disp_sym(num, sym):        print(sym*num, end='') #recusiondef hanoi(a, b, c, n, tray_num): if n == 1:  move_tray(a, c)  disp(tray_num)  sleep(0.7) else:  hanoi(a, c, b, n-1, tray_num)  move

  • 使用70行Python代码实现一个递归下降解析器的教程

     第一步:标记化 处理表达式的第一步就是将其转化为包含一个个独立符号的列表.这一步很简单,且不是本文的重点,因此在此处我省略了很多. 首先,我定义了一些标记(数字不在此中,它们是默认的标记)和一个标记类型: token_map = {'+':'ADD', '-':'ADD', '*':'MUL', '/':'MUL', '(':'LPAR', ')':'RPAR'} Token = namedtuple('Token', ['name', 'value']) 下面就是我用来标记 `expr` 表

  • python中尾递归用法实例详解

    本文实例讲述了python中尾递归用法.分享给大家供大家参考.具体分析如下: 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的.当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归.尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码. 原理: 当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的.编译器可以做到这点,因

  • 关于尾递归的使用详解

    关于尾递归的使用详解

    这几天看到几篇关于尾递归的文章,之前对尾递归没有多大概念,所以回头研究了一下尾递归. 尾递归的概念尾递归(Tail Recursion)的概念是递归概念的一个子集.对于普通的递归,由于必须要记住递归的调用堆栈,由此产生的耗用是难以估量的.比如下文中php小节第一个例子使用php写一个阶乘函数,就是由于递归造成了栈溢出的错误.尾递归出现的目的就是消除递归栈耗损这个缺憾的. 从代码层面看,尾递归其实一句话就可以说清楚了: 函数的最后一个操作是递归调用 比如"菲波纳锲"数列的php的递归实现

  • C#中的尾递归与Continuation详解

    这几天恰好和朋友谈起了递归,忽然发现不少朋友对于"尾递归"的概念比较模糊,网上搜索一番也没有发现讲解地完整详细的资料,于是写了这么一篇文章,权当一次互联网资料的补充.:P 递归与尾递归 关于递归操作,相信大家都已经不陌生.简单地说,一个函数直接或间接地调用自身,是为直接或间接递归.例如,我们可以使用递归来计算一个单向链表的长度: 复制代码 代码如下: public class Node {     public Node(int value, Node next)     {     

  • 详解Python如何实现尾递归优化

    详解Python如何实现尾递归优化

    目录 一般递归与尾递归 一般递归 尾递归 C中尾递归的优化 Python开启尾递归优化 一般递归与尾递归 一般递归 def normal_recursion(n): if n == 1: return 1 else: return n + normal_recursion(n-1) 执行: normal_recursion(5)5 + normal_recursion(4)5 + 4 + normal_recursion(3)5 + 4 + 3 + normal_recursion(2)5 +

  • 详解Kotlin中的变量和方法

    详解Kotlin中的变量和方法 变量 Kotlin 有两个关键字定义变量:var 和 val, 变量的类型在后面. var 定义的是可变变量,变量可以被重复赋值.val 定义的是只读变量,相当于java的final变量. 变量的类型,如果可以根据赋值推测,可以省略. var name: String = "jason" name = "jame" val max = 10 常量 Java 定义常量用关键字 static final, Kotlin 没有static,

  • C++ 实现汉诺塔的实例详解

    C++ 实现汉诺塔的实例详解 前言: 有A,B,C三塔,N个盘(从小到大编号为1-N)起初都在A塔,现要将N个盘全部移动到C塔(按照河内塔规则),求最少移动次数以及每次的移动详细情况. 要求: 需要采用递归方法和消除尾递归两种方法编写. 盘数N由用户从标准输入读入,以一个整数表示,然后请调用两个方法按照下面例子所述分别在屏幕中输出结果(正常情况下一个输入数据会显示同样的输出结果2次). 实现代码: #include<iostream> using namespace std; void mov

  • 详解JS中的reduce fold unfold用法

    fold(reduce) 说说reduce吧, 很喜欢这个函数,节省了不少代码量,而且有一些声明式的雏形了,一些常见的工具函数,flatten,deepCopy,mergeDeep等用reduce实现的很优雅简洁.reduce也称为fold,本质上就是一个折叠数组的过程,把数组中的多个值经过运算变成一个值,每次运算都会有一个函数处理,这个函数就是reduce的核心元素,称之为reducer,reducer函数是个2元函数,返回1个单值,常见的add函数就是reducer const addRed

  • 详解Python中递归函数的原理与使用

    详解Python中递归函数的原理与使用

    目录 什么是递归函数 递归函数的条件 定义一个简单的递归函数 代码解析 内存栈区堆区 死递归 尾递归 实例 什么是递归函数 如果一个函数,可以自己调用自己,那么这个函数就是一个递归函数. 递归,递就是去,归就是回,递归就是一去一回的过程. 递归函数的条件 一般来说,递归需要边界条件,整个递归的结构中要有递归前进段和递归返回段.当边界条件不满足,递归前进,反之递归返回.就是说递归函数一定需要有边界条件来控制递归函数的前进和返回. 定义一个简单的递归函数 # 定义一个函数 def recursion

  • AngularJS 日期格式化详解

    AngularJS是为了克服HTML在构建应用上的不足而设计的.HTML是一门很好的为静态文本展示设计的声明式语言,但要构建WEB应用的话它就显得乏力了.所以我做了一些工作(你也可以觉得是小花招)来让浏览器做我想要的事. AngularJS的日期格式化有两种形式,一种是在HTML页面,一种是在JS代码里,都是用到AngularJS的过滤器$filter. HTML: date_expression 即 你在$scope中设的date类型变量(注意,一定是date object才正确), 也是要显

  • spring boot的maven配置依赖详解

    spring boot的maven配置依赖详解

    本文介绍了spring boot的maven配置依赖详解,分享给大家,具体如下: 我们通过引用spring-boot-starter-parent,添加spring-boot-starter-web 可以实现web项目的功能,当然不使用spring-boot-start-web,通过自己添加的依赖包也可以实现,但是需要一个个添加,费时费力,而且可能产生版本依赖冲突.我们来看下springboot的依赖配置: 利用pom的继承,一处声明,处处使用.在最顶级的spring-boot-dependen

随机推荐