递归

向右看齐 2022-05-03 10:28 251阅读 0赞

递归优点：代码简单 代码量少  
递归缺点：不易理解

用递归解决问题时，主要思路：  
1.将一个大问题分解成子问题  
2.子问题除了问题规模会变小，和原问题解决的思路是一样的，即调用函数本身解决子问题  
3.要存在一个临界值使得循环可以停止

下面列举几个例子：

### 1.求阶乘 ###

public class TestDemo {
        
       //递归求阶乘 	
    	public static int fac(int n) {
        
            	int tmp = 1;
            	if(n == 1) {
        
                	tmp = 1;
                	return tmp;
            	} else {
        
                	tmp = fac2(n-1)*n;
                	return tmp;
            	}
        	}
        
     	public static void main(String[] args) {
        
            	System.out.println(fac(5));//120        	     
        	}
    	}

在fac()方法中，每次的tmp值都是当前n值和fac(n-1)的值相乘进行循环，而当n=1，即趋于某个临界值，就会有数值返回，最后可以得到要求的结果

### 2.斐波那契数列求和的递归 ###

public static int fibSum(int n) {
        
            if (n <= 0) {
        
                return -1;
            }
            int sum = 1;
            if (n == 1) {
        
                return sum;
            } else if (n == 2) {
        
                return ++sum;
            } else {
        
                sum = sum + (fibSum(n - 1) + fibSum(n - 2));
                return sum;
            }
        }

### 3.二分法求值的递归 ###

public static int binarySearch(int array[], int left, int right, int key) {
        
            int mid = (left + right) >> 1;
            if (left <= right) {
        
                if (key == array[mid]) {
        
                    return mid;
                } else if (key > array[mid]) {
        
                    return binarySearch(array, mid + 1, right, key);
                } else {
        
                    return binarySearch(array, left, mid - 1, key);
                }
            }
            return -1;
        }