【小白学算法】10.递归的调用机制、使用时要注意的规则

简单来说,递归就是自己调用自己,在每次调用时传入不同的变量。递归有助于解决复杂的问题,同时让代码变得简洁。
在之前的文章中,对递归有过简单的介绍,现在进一步了解下递归的调用机制。

一、递归的调用机制

先上一段简单的递归调用的代码:

package recursion;

public class RecursionTest {
    public static void main(String[] args) {
        test(4);
    }

    public static void test(int n) {
        if (n > 2) {
            test(n - 1);
        }
        System.out.println("n=" + n);
    }
}

可以看到,在main方法里,执行test(4),当满足n>2的条件时,test()会继续调用test(),直到不满足递归条件,打印出n的值。
运行结果其实也很容易想到:

n=2
n=3
n=4

Process finished with exit code 0

运行结果倒不是重点了,现在借着这段代码再加张图,看下递归的调用机制。

图中所示就是在执行代码的过程中,jvm中发生的一些事情。不过这里声明一下,关于jvm的某些描述可能并不是很准确,这里只是辅助理解记忆。

  1. 首先,在运行main方法时,会在栈里开辟一个main方法的栈帧。
    当main方法里调用test方法时,又会压入一个栈帧,也就是入栈。当方法没运行结束时,是不会出栈的。
    所以,运行test(4),会继续压入一个栈帧(红色箭头)。
  2. test(4)里,经过判断会继续调用test(3),于是继续压入一个栈帧。
  3. test(3)里,经过判断会继续调用test(2),于是继续压入一个栈帧。
  4. test(2)里,经过判断,不再递归,于是运行了print代码,打印出n的值为2。
    方法运行完了就会出栈(黄色箭头),回到test(3)
  5. test(3)打印出n的值为3,继续出栈,回到test(4)
  6. test(4)打印出n的值为4,main方法运行结束,退出程序。

所以,代码运行的结果就是2,3,4

二、使用递归需要知道的点

  1. 执行一个方法时,会创建一个新的受保护的独立空间。比如上面的栈帧。
  2. 方法的局部变量是独立的,不会相互影响。比如上面每次递归时候的变量n
    但是,如果方法中使用的是引用类型变量,那会共享该引用类型。比如,引用一个数组。
  3. 重点:递归必须向退出递归的条件逼近,否则就无限递归,最终栈溢出StackOverflowError
  4. 当方法执行完毕,或者遇到return,就会返回。遵守谁调用,就将结果返回给谁。
    比如上图中最上面的栈帧test(2)运行结束后,就返回到调用它的test(3)
文章来自全网采集,如有侵权请联系我们删除,aarocn@163.com
愉悦心情 » 【小白学算法】10.递归的调用机制、使用时要注意的规则

提供最优质的资源集合

立即查看 了解详情