递归相关知识(java)版

递归递归小题练习

 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 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);    }*/}

递归时间复杂度分析