3.4 数据结构之递归

递归

定义：计算机科学中，递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小自己

说明：

1.自己调用自己，如果说每个函数对应这一种解决方案，自己调用自己意味着解决方案是一样的（有规律的）

2.每次调用，函数处理的数据会较上次缩减（子集），而且最后会缩减至无需继续递归

3.内层函数调用（子集处理完成），外层函数才能算调用完成。

解题思路：

1.确定能否使用递归求解

2.推导出递推关系，即父关系与子问题的关系，以及递归的结束条件

深入到最里层叫做递
从里层里出来叫做归
在递的过程中，外层函数内的局部变量（以及方法参数）并未消失，归的时候还可以用到

例1-阶乘

用递归方法求解

阶乘的定义 n!=1·2·3···（n-2)·（n-1)·n，其中n为自然数，当然0！=1
递推关系

f(n) = 1 n==1

f(n) = n* f (n-1) n>1

例2- 反向打印字符串

import java.util.*;public class Main {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");}
}

递归二分查找

 public static int search(int[] a,int target){return -1;}private static int f(int[] a, int target,int i ,int j){if(i>j){return -1;}int m=(i+1)>>>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 void main(String[] args)  {f(0,"abcd");}

递归冒泡排序

将数组分成两部分，[0...j] [j+1......a.length-1]

左边[0....j]是未排序部分。

右边是已排序部分

未排序区间内，相邻的两个元素比较，如果前一个大于后一个，则交换位置。

    public static void sort(int[] a){bubble(a,a.length-1);}private static void bubble(int[] a,int j){if(j==0){return;}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;}}bubble(a,j-1);}

递归--插入排序

  public static void sort(int[] a){insertion(a,1);}//low:未排序元素的下边界private static void insertion(int[] a,int low){if(low==a.length){return;}int t=a[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);}//另一种插入排序的实现(赋值次数比较多，跟循环有关系，3*n次赋值，效率会低）private static void insertion2(int[] a,int  low){if(low==a.length){return;}int i =low-1;while(i>=0 && a[i]>a[i+1]){int t=a[i+1];a[i]=a[i-1];a[i+1]=t;i--;}insertion(a,low+1);}

递归求斐波那契数列第n项

每个递归函数例包含多个自身调用，称之为multi recursion

public class E06Fibonacci {public static int f(int n){if(n==0){return 0;}if(n==1){return 1;}return f(n-1)+f(n-2);}
}

递归次数：2*f(n+1) -1

变体1-兔子问题

改进：使用Memoization（记忆法，也称备忘录）进行改进

Params: n-第n项

Returns：第n项的值

public static int fibonacci(int n){int[] cache=new int[n+1];Arrays.fill(cache,-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;}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=fibonacci(8);System.out.println(f);}