精华内容
下载资源
问答
  • 递归效率问题及递归与循环比较
    2021-02-12 19:58:31

    1.所谓的递归慢到底是什么原因呢?

    大家都知道递归的实现是通过调用函数本身,函数调用的时候,每次调用时要做地址保存,参数传递等,这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括:局部变量、形参、调用函数地址、返回值。那么,如果递归调用N次,就要分配N*局部变量、N*形参、N*调用函数地址、N*返回值。这势必是影响效率的。

    2.用循环效率会比递归效率高吗?

    递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就一定比递归高,递归和循环是两码事,递归带有栈操作,循环则不一定,两个概念不是一个层次,不同场景做不同的尝试。

    2.1递归算法:

    优点:代码简洁、清晰,并且容易验证正确性。(如果你真的理解了算法的话,否则你更晕)

    缺点:它的运行需要较多次数的函数调用,如果调用层数比较深,需要增加额外的堆栈处理(还有可能出现堆栈溢出的情况),比如参数传递需要压栈等操作,会对执行效率有一定影响。但是,对于某些问题,如果不使用递归,那将是极端难看的代码。

    2.2循环算法:

    优点:速度快,结构简单。

    缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话,最好使用循环。

    2.3递归算法和循环算法总结:

    1. 一般递归调用可以处理的算法,也通过循环去解决常需要额外的低效处理。

    2. 现在的编译器在优化后,对于多次调用的函数处理会有非常好的效率优化,效率未必低于循环。

    3.递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环替换,而不影响程序的阅读,那么替换成递归往往是好的。(例如:求阶乘的递归实现与循环实现。)

    3.那么递归使用的栈是什么样的一个栈呢?

    首先,看一下系统栈和用户栈的用途。

    3.1系统栈(也叫核心栈、内核栈)是内存中属于操作系统空间的一块区域,其主要用途为: (1)保存中断现场,对于嵌套中断,被中断程序的现场信息依次压入系统栈,中断返回时逆序弹出; (2)保存操作系统子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。

    3.2用户栈是用户进程空间中的一块区域,用于保存用户进程的子程序间相互调用的参数、返回值、返回点以及子程序(函数)的局部变量。

    我们编写的递归程序属于用户程序,因此使用的是用户栈。

    更多相关内容
  • 1.所谓的递归慢到底是什么原因呢? 大家都知道递归的实现是通过调用函数本身,函数调用的时候,每次调用时 要做地址保存,参数传递等,这是通过一个递归工作栈实现的...2.用循环效率会比递归效率高吗? 递归与循环是...

    1.所谓的递归慢到底是什么原因呢?

    大家都知道递归的实现是通过调用函数本身,函数调用的时候,每次调用时
    要做地址保存,参数传递等,这是通过一个递归工作栈实现的。具体是每次
    调用函数本身要保存的内容包括:局部变量、形参、调用函数地址、返回值。
    那么,如果递归调用N次,就要分配N*局部变量、N*形参、N*调用函数地址、
    N*返回值。这势必是影响效率的。
    

    2.用循环效率会比递归效率高吗?

    递归与循环是两种不同的解决问题的典型思路。当然也并不是说循环效率就
    一定比递归高,递归和循环是两码事,递归带有栈操作,循环则不一定,两
    个概念不是一个层次,不同场景做不同的尝试。
    

    2.1递归算法:

    优点:代码简洁、清晰,并且容易验证正确性。(如果你真的理解了算法的
    话,否则你更晕)
    
    缺点:它的运行需要较多次数的函数调用,如果调用层数比较深,需要增加
    额外的堆栈处理(还有可能出现堆栈溢出的情况),比如参数传递需要压栈
    等操作,会对执行效率有一定影响。但是,对于某些问题,如果不使用递归,
    那将是极端难看的代码。
    

    2.2循环算法:

    优点:速度快,结构简单。
    
    缺点:并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用
    循环并不困难的话,最好使用循环。
    

    2.3递归算法和循环算法总结:

    1. 一般递归调用可以处理的算法,也通过循环去解决常需要额外的低效处理。
    
    2. 现在的编译器在优化后,对于多次调用的函数处理会有非常好的效率优化
    ,效率未必低于循环。
    
    3.递归和循环两者完全可以互换。如果用到递归的地方可以很方便使用循环
    替换,而不影响程序的阅读,那么替换成递归往往是好的。(例如:求阶乘
    的递归实现与循环实现。)
    

    3.那么递归使用的栈是什么样的一个栈呢?首先,看一下系统栈和用户栈的用途。

    3.1系统栈(也叫核心栈、内核栈)是内存中属于操作系统空间的一块区域,
    其主要用途为: (1)保存中断现场,对于嵌套中断,被中断程序的现场信息
    依次压入系统栈,中断返回时逆序弹出; (2)保存操作系统子程序间相互调
    用的参数、返回值、返回点以及子程序(函数)的局部变量。
    
    3.2用户栈是用户进程空间中的一块区域,用于保存用户进程的子程序间相互
    调用的参数、返回值、返回点以及子程序(函数)的局部变量。
    
    我们编写的递归程序属于用户程序,因此使用的是用户栈。
    
    展开全文
  • 优化递归效率zz

    2021-04-23 07:07:27
    函数递归调用是很常见的做法,但是它往往是低效的,本文探讨优化递归效率的思路。1、尾递归转换成迭代尾递归是一种简单的递归,它可以用迭代来代替 比如 求阶乘函数的递归表达 int f( int n) {if(n<=0)return 1;...

    函数递归调用是很常见的做法,但是它往往是低效的,本文探讨优化递归效率的思路。

    1、尾递归转换成迭代

    尾递归是一种简单的递归,它可以用迭代来代替 比如 求阶乘函数的递归表达

    7fb4027ec5830a04616fbcae9e46d5b8.png int f( int n)

    7ea44f1a15e4cb23e75f01d619e3d62c.png {

    a1d082ba3978b59bc6ac33e532442564.pngif(n<=0)return 1;

    cbec3f219a68959eb766dc8ae9dd4c3e.pngreturn n*f(n-1);

    0f3fc47a567ff5658f1af4cd0a37f4e3.png}

    可以转换成完全等价的循环迭代

    cf064e98ff250ea1c361a1f36541165b.png int f( int n)

    74790f408668fbbcc4d808454df7b5e7.png {

    a8e190e9f01990036918a470866d956b.pngint r=0;

    9731e2a9eb71c209bf5e957fa6e101a2.pngwhile(n-->0)

    a8aa0ab6b147a9cffdce22aebe185025.png r*=n;

    ec1cc69c3d1f1eddcde6de29cb6ab48f.pngreturn r;

    da0701cf8c236af3f63d7280a41d1979.png}

    尾递归是最简单的情形,好的编译器甚至可以自动的识别尾递归并把它转换成循环迭代。

    2、动态规划

    我一直把动态规划看作尾递归的推广(个人观点),在2维或更高的情况下,直接使用递归会造成大量的重复计算,例如在斐波那契数列的递归关系 Fib(n+2)=Fib(n+1)+Fib(n)中 Fib(3)在计算Fib(4)和Fib(5)都会用到 他被重复计算了2遍,当数列长度增大时 这种浪费会变得越来越明显。

    动态规划方法将可能需要的结果全部计算出来 并保存 一般来说 动态规划从最小数开始 自底向上计算所有值(因为后面的结果会用到前面的结果) 直到得到的结果中包含了要求的结果。

    9b384dcad4ad52313e5fe5919d9b1e21.png int Fib(unsigned n)

    a4a87a41f7981689ff58712ec767654a.png {

    e013fd93079f409b2d99b73c37c6e9a7.pngif(n==1)return 1;

    bed7a472ff033b699d35a3b440391298.pngif(n==0)return 0;

    ed6a1c2fdd1762daa80b5498cd67f7d7.pngreturn Fib(n-1)+Fib(n-2);

    98a5d77b79416c83a8bdaaa06cd173a4.png}

    c96ec131e5cabcf6088be7b244b309ce.png

    12c726e8defdb152014e87de0f72c136.png

    0447de2dba7e34a6c885865af44f008d.png int Fib(unsigned n)

    e06c5722d05bd9e4074fab720720a461.png {

    8fd2f48cb398c408595c0fe226fd7c5b.pngint* f=new int[n+1];

    1ac11a8e066f4ec7a6e0afc521f1d6cf.png f[1]=1;f[0]=0;

    5c7d7e19b267ff5a1d8636684b973ae6.pngfor(int i=0;i<=n;i++);

    90ee89ee6427eaba4337513be684d35a.png f[i]=f[i-1]+f[i-2];

    277545c0e5388200ba3af2da16c1d4a5.pngint r=f[n];

    46c81c0ec84a556aa8c76f022e68fc75.png delete[] f;

    dee7a63441455db60bb81fa9f0bb140f.pngreturn r;

    1eaf702e6569262786e04d38ea808ed4.png}

    动态规划不会造成重复运算 但是 它可能计算不需要的结果 例如关系式

    a(n)=a(n-2)+a(n-4);

    使用动态规划会计算很多不需要的结果,尽管如此,它的效率远远高于直接递归运算。

    实际上,大部分时候动态规划把指数级时间复杂度的递归运算变成了多项式级时间复杂度的递推。

    3、备忘录

    减少重复值的另一个方法是使用备忘录,每次成功计算一个结果 ,就将它存入备忘录中,当再次遇到此问题时,无需重复计算,直接取出即可。

    备忘录方法和直接递归相似,只是在函数在计算之前先访问备忘录,如果在备忘录中找到,就无须再计算,直接返回。

    备忘录结构可以使用关联数组 哈希表等实现,特别地,当递归参数是整数时 直接用数组就可以了。

    与动态规划相比,备忘录消耗了额外的备忘录查找时间,并且和直接递归一样 有大量的多余函数调用开销,但它不会造成额外计算。

    4、内联

    这是来自Efficient C++的方法,C++编译器不会把递归函数内联,这样,函数调用的开销变得很大。为了提高效率,必须手动内联函数。

    递归函数无法完全内联,但是我们可以把它展开,这是前面Fibnacci函数的一层展开

    133d97c1a4231d1a24ee9db7ac825a7a.png int Fib(unsigned n)

    c41aae076f7aac626f8eaea0f2a1ec97.png {

    9d8425dbd50d87c2a13482bc41153137.pngif(n==1)return 1;

    e38f4c9a742549786571d0390fb9410f.pngif(n==0)return 0;

    b165581086ef5a7c31b93cf4450667fd.png

    2af27644d65beac0140a9937e504b3b2.pngint fn1,fn2;

    8b3edfbda9a003fee1fdf3a908e49694.pngif(n-1==1)fn1=1;

    f39199d9d65e2118bd5e46b9a7cf4533.pngelse if(n-1==0)fn1=0;

    15b977b4c64ba224a52341063e5a274f.pngelse fn1=Fib(n-2)+Fib(n-3);

    7ae4728e23efceb8136229be41162d58.png

    df12378d91885249ea7af79a642c4380.pngif(n-2==1)fn2=1;

    6345b552cf6c2a70a7c57b230f0a47c6.pngelse if(n-2==0)fn2=0;

    0fd373c051680b04dbd425791d0e9156.pngelse fn2=Fib(n-3)+Fib(n-4);

    55ba851211a4d64f82765c8d960acf58.png

    b00ba8933017ec0cbe46a2c271717d82.pngreturn fn1+fn2

    7604deea761a7ee9ba7cb74aefa2a590.png}

    5、解递归

    尽管我们倾向于虐待计算机 让它帮我们处理较复杂的问题,但是很多时候我们需要获得效率,就必须自己动手,其实很多递归式可以手动解出,组合数学为我们提供了不少工具:

    (1)解齐次递归方程

    简单的递归方程可以按以下步骤求解:

    解Fibonacci函数的递归方程

    36_47.png

    首先把它转换成下面的式子

    36_48.png

    这个代数方程被称为递归方程的特征方程,下一步是解特征方程求出它的所有解,对这个例子来说

    36_49.png

    根据组合数学的结论

    36_50.png

    再由

    F(0)=0和F(1)=1可以得出方程组

    36_51.png

    解这个方程组可得到a和b的值

    36_52.png

    代入前面的公式可以求出Fibnacci通项公式

    36_53.png

    验证后可以知道,这个公式是正确的,显然用此公式做浮点运算,比使用递归方式快得多。

    (2)母函数

    组合数学中还提供了一种更强有力的处理手段:生成函数(又称为母函数)

    仍然以求解Fibonacci数列为例,为了易于理解,我这里把生成函数描述成一个以Fibonacci数列为系数的多项式。即

    36_54.png

    现在考虑这样一个多项式

    36_55.png

    按g(x)的定义,可以这样展开

    36_56.png

    36_57.png

    36_58.png

    这个时候不要忘记我们的递推公式,可以进一步化简为

    36_59.png

    这个式子与g(x)非常像,将它两边同时乘以x

    36_60.png

    36_61.png

    36_62.png

    再整理一下等式

    36_63.png

    利用F(0)=0,F(1)=1可以求出

    36_64.png

    这样 我们求出了g(x),等等,g(x)是什么来着?不是以Fibonacci数列为系数的多项式么?现在求出的东西是什么?不要急,用泰勒级数展开就能得到通项公式了,结果跟上面的是一样的。(太麻烦了,略过略过^_^)

    https://www.cnblogs.com/end/category/82543.html

    展开全文
  • packagecom.changhong.csc.ie.mdm.test....importjava.util.ArrayList;importjava.util.HashMap;importjava.util.List;importjava.util.Map;importcom.alibaba.fastjson.JSON;public classTreeTest {privateInteger...

    packagecom.changhong.csc.ie.mdm.test.org;importjava.util.ArrayList;importjava.util.HashMap;importjava.util.List;importjava.util.Map;importcom.alibaba.fastjson.JSON;public classTreeTest {privateInteger id;privateInteger pId;privateString name;private Listchildren;publicTreeTest() {

    }publicTreeTest(Integer id, Integer pId, String name) {super();this.id =id;this.pId =pId;this.name =name;

    }publicInteger getId() {returnid;

    }public voidsetId(Integer id) {this.id =id;

    }publicInteger getpId() {returnpId;

    }public voidsetpId(Integer pId) {this.pId =pId;

    }publicString getName() {returnname;

    }public voidsetName(String name) {this.name =name;

    }public ListgetChildren() {returnchildren;

    }public void setChildren(Listchildren) {this.children =children;

    }

    @OverridepublicString toString() {return "TreeTest [id=" + id + ", pId=" + pId + ", name=" +name+ ", children=" + children + "]";

    }//测试数据

    public static voidmain(String[] args) {

    List list = new ArrayList();

    Map map = new HashMap();

    TreeTest terr1= new TreeTest(1, 0, "一级父节点");

    TreeTest terr2= new TreeTest(2, 1, "一级1子节点");

    TreeTest terr3= new TreeTest(3, 2, "一级2子节点");

    TreeTest terr4= new TreeTest(4, 0, "二级父节点");

    TreeTest terr5= new TreeTest(5, 4, "二级1子节点");

    TreeTest terr6= new TreeTest(6, 4, "二级1子节点2");

    TreeTest terr7= new TreeTest(7, 3, "一级3子节点");

    TreeTest terr8= new TreeTest(8, 5, "二级2子节点");

    map.put(terr1.getId(), terr1);

    map.put(terr2.getId(), terr2);

    map.put(terr3.getId(), terr3);

    map.put(terr4.getId(), terr4);

    map.put(terr5.getId(), terr5);

    map.put(terr6.getId(), terr6);

    map.put(terr7.getId(), terr7);

    map.put(terr8.getId(), terr8);/** List li = getChildren(map,0,1);

    *

    * System.out.println(JSON.toJSON(li));*/Map> treemap = new HashMap>();for(TreeTest treeTest : map.values()) {

    List listTree =treemap.get(treeTest.getpId());if (listTree == null) {

    listTree= new ArrayList();

    listTree.add(treeTest);

    treemap.put(treeTest.getpId(), listTree);

    }else{

    List ordTree =treemap.get(treeTest.getpId());

    ordTree.add(treeTest);

    treemap.put(treeTest.getpId(), ordTree);

    }

    }

    List lists = new ArrayList();

    lists.add(terr1);

    List li =getChildren(lists, treemap);

    System.out.println(JSON.toJSON(li));

    }//递归树

    public static List getChildren(Listtrees,

    Map>children) {

    List childrenTree = null;for(TreeTest tree : trees) {//获得子节点

    childrenTree =children.get(tree.getId());if (childrenTree != null) {//添加子节点

    tree.setChildren(childrenTree);//递归

    getChildren(tree.getChildren(), children);

    }

    }returnchildrenTree;

    }

    }

    展开全文
  • Java递归算法

    2020-12-22 17:40:01
    Java递归算法是基于Java语言实现的递归算法。  递归算法的实质是把问题分解成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效,它可以使算法简洁和易于理解。  ...
  • /*** 参数递归和迭代的效率,递归效率太低,如果用到递归一般使用循环*/public class TestRecursion {public static void main(String[] args) {//标记递归方法开始执行事件long d1=System.currentTimeMillis();...
  • java递归是什么意思,java递归怎么用?程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。但是如果没终止条件会造成死循环,所以递归代码里要有结束自调自的条件。接下来通过...
  • Java递归的深入理解

    2021-03-11 13:31:49
    今天爱站技术频道的小编将给您带来这篇对Java递归的深入理解,一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,需要...
  • 递归循环出某个文件夹下面的所有的文件夹以及文件在关联文件表查找文件的内容这是正确的做法,感兴趣的朋友可以了解下,或许对你学习oracle递归有所帮助
  • java 递归函数

    2021-02-12 16:08:27
    这就是递归二、为什么要用递归递归的目的是简化程序设计,使程序易读三、递归的弊端:尽管非递归函数效率高,但较难编程,可读性较差。递归函数的缺点是添加了系统开销,也就是说,每递归一次,栈内存就多占用一截...
  • Java递归算法是基于Java语言实现的递归算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解。递归算法对解决一大类问题很有效,它可以使算法简洁和易于理解。递归算法...
  • 程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题...
  • 文章目录6.1 什么是递归?6.2 手写递归的三个要素6.2.1 第一要素: 明确你这个函数想要干什么6.2.2 第二要素: 寻找递归结束的条件6.2.3 第三要素: 找出函数的等价关系式(递推式)6.3 栗子的磨练1. 递归打印n次字符串2. ...
  • Java递归

    2021-05-19 01:27:47
    经过适当处理,尾递归形式的函数的运行效率可以被极大地优化。尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化(称为“尾调用消除”),但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度...
  • 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 要求: 必须采用顺序存储结构。 必须按关键字大小有序排列。...
  • java递归和循环

    万次阅读 2018-12-21 12:56:44
    递归递归的基本思想就是“自己调用自己”,一个使用递归技术的方法将会直接或者间接的调用自己。 StackOverflowError:当应用程序递归太深而发生堆栈溢出时,抛出该错误。 递归结构 1:递归尽头:什么时候不...
  • java递归遍历树形list

    千次阅读 2020-06-09 15:02:37
    是遍历树形List,不是生成。当然,因为子节点个数的不确定性,所以,不论是生成树还是遍历树,都得用到递归 网上查了一圈,基本都是生成,不是遍历一棵树形List。...java递归遍历树结构目录 坑啊。 自己写一个了: ...
  • Java递归求和的两种简单方法(推荐)方法一:package com.smbea.demo;public class Student {private int sum = 0;/*** 递归求和* @param num*/public void sum(int num) {this.sum += num--;if(0 < num){sum(num...
  • 展开全部一、递归算法基本思路:Java递归算法是基于Java语言实现的递归算法。递归算法是一e5a48de588b662616964757a686964616f31333363373166种直接或者间接调用自身函数或者方法的算法。递归算法实质是把问题分解成...
  • 1.何为递归个人理解就是自己调用自己,直到满足一个条件结束自己调用自己的过程,这个就是递归。举一个通俗的点的例子:假设你在一个电影院,你想知道自己坐在哪一排,但是前面人很多,你懒得去数了,于是你问前一排...
  • 一、含义程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与...
  • 在写一个算法中,由于递归调用次数过多,堆栈溢出。堆栈的大小是系统控制的,无法改变。如果递归调用出现问题,可以考虑采取循环的方式来解决,将需要的数据在关键的调用点保存下来使用。简单的说,就是用自己的数据...
  • 递归是一种常见的解决问题的方法,即把问题逐渐简单化,递归的基本思想就是“自己调用自己”,一个使用递归技术的方法将会直接或者间接的调用自己。 利用递归可以简单的程序来解决一些复杂的问题,eg:斐波那契数列...
  • 递归算法,用Java的BigDecimal类package com.todo.first;import java.io.BufferedWriter;import java.io.File;import java.io.FileWriter;import java.io.IOException;import java.math.BigDecimal;import java.util...
  • 但是,不适合的递归往往导致程序的执行效率变低。一、递归算法基本思想递归算法即在程序中不断反复调用自身来叨叨求解问题的方法。此处的重点是调用自身,这就要求待求解的问题能够分解为相同问题的一个子问题。这样...
  • 递归调用循环次数太多,求救,效率很慢 list大小3000+, 当想着循环时发现父节点挂接到父节点的时候,减小list大小来减少循环次数,却报错, 希望能得到帮助,如何优化,重写? 代码中只能得到根节点的ID !...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 81,904
精华内容 32,761
关键字:

java递归效率

java 订阅
友情链接: decl7s.rar