递归

递归小题练习

 public static int f(int n){
        if(n==1){
            return 1;
        }
        return n*f(n-1);
    }

    public static void main(String[] args) {
        int f=f(5);
      }

递归反向打印字符串-c的话,就正序,java正逆无所谓

public static void f(int n,String str){
        if(n==str.length()) {
           return;
        }
        f(n+1,str);
        System.out.println(str.charAt(n));
    }

    public static void main(String[] args) {
        f(0,"abcd");
    }

递归二分查找

//递归二分查找
    /*
    递归子问题函数
Params:a-数组
target-待查找值
i-起始索引包含
j-结束宗引〔包含)
Returns:
找到返回索引
规不到返回-1
     */
/*
    private static int f(int []a,int target,int i,int j){
        if(i>j){
            return -1;
        }
        int m=(i+j)>>>1;
        if(target<a[m]){
            return f(a,target,i,m-1);
        }else if(a[m]<target){
            return f(a,target,m+1,j);
        }else {
            return m;
        }
    }
   public static int search(int[]a,int target){
        return f(a,target,0,a.length-1);
   }

递归冒泡排序

 //递归冒泡排序
/*    递归日泡排序
◆将数组划分成两部分[0-】+1.a.length-1]
            ◆左边[0…力是未排序部分
·右边0+1.a.length-1]是已排序分
·未排序区间内，相阳的两个元素比较，如果前一个大于后一个，则交换位置*/
    //j代表排序区域右边界
/*
  private static void bubble(int[]a,int j){
      if(j==0){
          return;
      }
      int x=0;
      for (int i = 0; i < j; i++) {
          if(a[i]>a[i+1]){
              int t=a[i];
              a[i]=a[i+1];
              a[i+1]=t;
              x=i;
          }
      }
      bubble(a,x);
  }

  public static void sort(int[]a){
      bubble(a,a.length-1);
  }

  public static void main(String[]args){
      int[]a={6,5,4,3,2,1};
      */
/*System.out.println(a.length-1);*//*

      System.out.println(Arrays.toString(a));
      bubble(a,a.length-1);
      System.out.println(Arrays.toString(a));
  }
*/
//递归-插入排序--区间插入排序

递归插入排序

    public static void sort(int[]a){
           insertion(a,1);
    }
    private static void insertion(int[]a,int low){
        if(low==a.length){
            return;
        }

        int t=a[low];//low是未排序区域的左边界
        int i=low-1;//已排序区域指针

        while (i>=0&&a[i]>t){//没有找到插入位置
            a[i+1]=a[i];
            i--;
        }

        //找到插入位置
        if(i+1!=low) {
            a[i + 1] = t;
        }
        insertion(a,low+1);
    }
}

递归求斐波那契额数列

//递归求斐波那契第n项
public class feibonaqie {
    public static int fibonacci(int n){
        int []cache=new int[n+1];
        Arrays.fill(cache,-1);
        cache[0]=0;
        cache[1]=1;//[0,1,-1,-1,-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 cache[n];
    }

    /*public static void main(String[] args) {
        int f=f(8);
        System.out.println(f);
    }*/
}

递归时间复杂度分析