:::tips

    • 注意递归函数的“宏观”语意
    • 递归函数就是一个函数，完成一个功能
    • 递归函数的调用，本质就是函数调用
    • 只不过调用的函数是自己而已
    • 程序调用的系统栈
    • 递归调用是有代价的:函数调用+系统栈空间 :::

    :::success 递归的本质：缩小问题的规模，在一个更小的问题里面来得到问题的解。 :::

    写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
    如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。

    image.png
    image.png

    1. public class Sum {
    2.     public static int sum(int[] arr){
    3.         return sum(arr,0);
    4.     }
    6.     private static int sum(int[] arr, int l){
    7.         if(l == arr.length){
    8.             return 0;
    9.         }
    10.         return arr[l] +sum(arr,l+1);
    11.     }
    13.     public static void main(String[] args) {
    14.         int[] nums  = {1,2,3,4,5,6,7,8,9};
    15.         System.out.println(sum(nums));
    16.     }
    17. }

    image.png