一文搞懂递归调用 ✨ 每日积累

一文搞懂递归调用

递归是什么

递归做为一种算法在程序设计语言中广泛应用。但是如果没终止条件会造成死循环，所以递归代码里要有结束自调自的条件。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

简单递归示例代码

public class RecursionTest {
    private void testRecursion(int num){
        if (num > 9){
            testRecursion(num / 10);
        }
        System.out.println(num % 10);
    }
    public static void main(String[] args) {
        new RecursionTest().testRecursion(123);
    }
}

得到的结果

1
2
3

递归调用图解分析

不知道栈和栈帧的可以参考此文章（https://blog.csdn.net/asd1358355022/article/details/119192321），栈是内存结构中的部分结构的组成部分

局部变量表作用

栈帧中的局部变量表是一组变量值的存储地址，用于存放方法参数和方法内部定义的局部变量。如上图所示我们的方法入参就在局部变量表中存放。

递归可以解决的问题

把一个大问题拆解成一些小问题治之，小问题之间互不影响（栈帧隔离，互不干扰执行自己栈帧的流程）

各种数学问题，如8皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子问题（google编程大赛）

各种算法也会使用到递归，比如快排，归并排序，二分查找，分治算法等。

各种算法也会使用到递归，比如快排，归并排序，二分查找，分治算法等。