尾递归优化小记

Ververica 发布于2019-08-16 15:39 / 1124人阅读

摘要：前言一般地对于语言而言普通的递归调用是在虚拟机栈上完成的假如是一个递归方法那么在其内部再调用自己的时候假设为那么方法变量表将创建在方法栈帧之上从而形成了一个新的栈帧因此容易发现在递归思想中递归简化了问题的表达但牺牲了虚拟机栈中的内存空间普通

前言

一般地,对于java语言而言,普通的递归调用是在java虚拟机栈上完成的.假如a()是一个递归方法,那么在其内部再调用自己的时候,假设为a1(),那么a1()方法变量表将创建在a()方法栈帧之上,从而形成了一个新的栈帧.因此容易发现,在递归思想中,递归简化了问题的表达,但牺牲了虚拟机栈中的内存空间.

普通递归 斐波那契递归法

public static int fib(int num){
        if(num<2)
            return num;
        else
            return fib(num-2)+fib(num-1);
    }

对于上面的解法,很容易就会发现,不但属于普通递归,而且在计算fib(num-1)是重复了fib(num-2)的计算量,因此代码效率大打折扣.因此效率较高的写法可以用for循环计算,

public static int fib3(int n) {
        if (n < 2)
            return n;
        else {
            int pre = 0;
            int suf = 1;
            for (int i = 2; i <= n; i++) {
                int temp = suf;
                suf += pre;
                pre = temp;
            }
            return suf;
        }
    }

斐波那契尾递归优化

public class Main {
    public static void main(String[] args) {
        
        System.out.print(fib2(3, 0, 1));
    }


    public static int fib2(int count, int pre, int result) {
        if (count == 1)
            return result;
        else
            return fib2(--count, result, result + pre);
    }
}

性能对比

 public static void main(String[] args) {
        long time = new Date().getTime();

        int num=40;
        System.out.println(fib(num));
        System.out.println("普通递归调用用时:" + (new Date().getTime() - time) + "毫秒");

        time = new Date().getTime();
        System.out.println(fib2(num, 0, 1));
        System.out.println("尾递归优化调用用时:" + (new Date().getTime() - time) + "毫秒");

        time = new Date().getTime();
        System.out.println(fib3(num));
        System.out.println("for循环法调用用时:" + (new Date().getTime() - time) + "毫秒");
    }
    //输出
    /*
    102334155
    普通递归调用用时:674毫秒
    102334155
    尾递归优化调用用时:0毫秒
    102334155
    for循环法调用用时:0毫秒
    */

可以看出有明显差异,即使普通递归法计算量多了一半,时间除以2也是387毫秒,这也远远高于for循环和递归尾优化法.

尾递归优化思想

即递归方法return 直接返回方法,注意是直接返回方法,不能是方法加1个值等形式.这样在递归调用时,新方法会覆盖当前栈帧,达到节省栈空间的目的.因此也就不会有递归调用产生的栈溢出问题.

尾递归写法

斐波那契例:

//count作为计数,表示递归层次,
//pre代表前一个值
//result 表示当前值
 public static int fib2(int count, int pre, int result) {
        //层次减到1时返回计算结果
        if (count == 1)
            return result;
        else{
        //递归调用时,层次减1,前一项更新为当前项,所以填result,第三个参数即实现了倒数第二个参数加倒数第一个参数.
        return fib2(--count, result, result + pre);
        }
    }

总体而言参数的书写分为两部分

前部分为计数,后部分为计算,例如计算阶乘时候只需要两个参数,第一个计数,第二个存结果.

尾递归将全部信息放入了参数里,因此也就巧妙地避免了需要上一栈帧保存信息.

私有云服务器托管优化递归数据栈尾队列尾调用长尾词库

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73619.html

尾递归优化小记

摘要：前言一般地对于语言而言普通的递归调用是在虚拟机栈上完成的假如是一个递归方法那么在其内部再调用自己的时候假设为那么方法变量表将创建在方法栈帧之上从而形成了一个新的栈帧因此容易发现在递归思想中递归简化了问题的表达但牺牲了虚拟机栈中的内存空间普通前言一般地,对于java语言而言,普通的递归调用是在java虚拟机栈上完成的.假如a()是一个递归方法,那么在其内部再调用自己的时候,假设为a1...

张率功 2019-07-31 10:08 评论0 收藏0
尾递归优化小记

摘要：前言一般地对于语言而言普通的递归调用是在虚拟机栈上完成的假如是一个递归方法那么在其内部再调用自己的时候假设为那么方法变量表将创建在方法栈帧之上从而形成了一个新的栈帧因此容易发现在递归思想中递归简化了问题的表达但牺牲了虚拟机栈中的内存空间普通前言一般地,对于java语言而言,普通的递归调用是在java虚拟机栈上完成的.假如a()是一个递归方法,那么在其内部再调用自己的时候,假设为a1...

Drinkey 2019-08-26 13:34 评论0 收藏0
Python开启尾递归优化!

摘要：尾递归优化一般递归与尾递归一般递归执行可以看到一般递归每一级递归都产生了新的局部变量必须创建新的调用栈随着递归深度的增加创建的栈越来越多造成爆栈尾递归尾递归基于函数的尾调用每一级调用直接返回递归函数更新调用栈没有新局部变量的产生类似迭代的 Python尾递归优化一般递归与尾递归一般递归: def normal_recursion(n): if n == 1: ...

junnplus 2019-07-31 10:54 评论0 收藏0
尾调用和尾递归

摘要：执行完了，销毁调用栈中自己的记录，依次销毁和的调用帧，最后完成整个流程。尾递归定义先来看一下递归，当一个函数调用自身，就叫做递归。尾调用 1. 定义尾调用是函数式编程中一个很重要的概念，当一个函数执行时的最后一个步骤是返回另一个函数的调用，这就叫做尾调用。注意这里函数的调用方式是无所谓的，以下方式均可：函数调用: func(···) 方法调用: obj.meth...

goji 2019-08-22 16:09 评论0 收藏0
js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

摘要：根据该规则，返回第个斐波那契数。尾递归函数调用自身，称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事斐波那契数列是以下一系列数字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

赵连江 2019-08-23 11:38 评论0 收藏0