开发者社区> 问答> 正文

数据结构中的递归算法怎么理解?能否画个图表示一下?

数据结构中的递归算法怎么理解?能否画个图表示一下?

展开
收起
知与谁同 2018-07-19 09:43:15 1516 0
1 条回答
写回答
取消 提交回答
  • 社区管理员

    简单的解释:方法内调用它本身。

    传递和回归必须存在一个临界点:比如最内层被调用的方法内给了一个返回值,或者是最内存被调用方法结束,然后将结果返回给上一层的方法.,然后一层层结束,一层层返回。

    它的使用场景,比如会用递归来解决斐波那契数列、阶乘。。的问题。

    例子:给一个整数n:求1+2+3+.....+n的值


    首先是执行main()方法,main()方法进栈,然后调用main()方法中的add(5)方法,add(5)方法进栈。当执行到return add(4)+5时,add(5)方法会调用add(4)方法,add(4)方法进展,然后依次递归调用,直到add(1)方法进栈为止。

    当执行add(1)方法时,会首先进行判断if(n==1),然后满足条件,该方法返回一个整数 1(临界点),(这个返回值是返回给add(2)方法的),然后add(1)方法执行完毕,出栈。


    此时add(2)方法接收了add(1)方法的返回值,执行add(2)方法,最后走到return add(1)+2==return 1+2  ,add(2)方法执行完毕,将返回值返回给add(3)方法,出栈。

    然后依次执行add(3)、add(4)、add(5)。。依次出栈。具体步骤看下图:


    add(5)方法接受到前几个递归方法执行完毕后传来的值:1+2+3+4,执行它本身,return add(4)+5==return 1+2+3+4+5,将该结果返回给main()方法,add(5)出栈。递归结束


    main()方法接受到了add(5)方法返回值,15,打印输出,main()方法结束,出栈。

    2019-07-17 22:54:31
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
如何使用Tair增强数据结构构建丰富在线实时场景 立即下载
Apache Flink 流式应用中状态的数据结构定义升级 立即下载
图解算法小抄 立即下载