思路

例题

package 递归;public class 反向打印字符串 {public static void main(String[] args) {f("ABC",0);}static  void f(String str,int n){if (n==str.length()){return;}f(str,n+1);System.out.println(str.charAt(n)+"");}
}

多路递归

递归优化 -剪枝(记忆优化)

时间优化但是增加了空间成本，增加了空间复杂度。

package 递归;import java.util.Arrays;public class 记忆优化递归 {public static void main(String[] args) {System.out.printf("", fibonmacci(5));}
//    使用记忆法 改进
//    params:n-第n项
//    Returns:第n项的之public static int fibonmacci(int n){int [] cache = new int [n+1];Arrays.fill(cache,-1);//[-1,-1]cache[0]=0;cache[1]=1;return  f(n,cache);}public  static  int f(int n,int [] cache){
//        if (n==0) {
//            return 0;
//        }
//        if (n==1) {
//            return 1;
//        }if (cache[n]!=-1) {return cache[n];}int x=f(n-1,cache);int y=f(n-2,cache);cache [n] =x+y;//存储当前计算的值return x+y;}
}

递归-爆栈问题

尾调用和尾递归

使内存能够得到及时的释放，某些编译器可以对尾调用做优化