Java-递归

递归就是以此类推的意思,即自己调用自己。因此使用递归有两个前提:可重复+能停止。

递归例子

一、阶乘

package com.joeaaa.demo04;
/*
*  1!+2!+3!+...+10!
*/
public class recursion {
    public static void main(String[] args) {
        System.out.println("result: "+ sum(10));
    }
    // 各项相加
    public static double sum(int num){
        if(num == 1) return 1;
        return multi(num)+sum(num-1);
    }
    // 相乘
    public static double multi(int num){
        if(num==1) return 1;
        return num*multi(num-1);
    }
}

二、斐波那契数列

Fib(n)=Fib(n-1)+Fib(n-2)

1、1、2、3、5、8、13、21.....
package com.joeaaa.demo04;

public static int fib(int n) throws Exception {
    if (n < 0)
        throw new Exception("negative!");
    else if (n == 0 || n == 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

三、归并排序

将序列分为若干有序序列(开始为单个记录),两个相邻有序的序列合并成一个有序的序列,以此类推,直到整个序列有序。

package com.joeaaa.demo04;

//递归过程是:在递进的过程中拆分数组,在回归的过程合并数组
public static void mergeSort(int[] source, int[] temp, int first, int last) {
    if (first < last) {
        int mid = (first + last) / 2;
        mergeSort(source, temp, first, mid);    //归并排序前半个子序列
        mergeSort(source, temp, mid + 1, last); //归并排序后半个子序列
        merge(source, temp, first, mid, last);    //在回归过程中合并
    } else if (first == last) {                    //待排序列只有一个,递归结束
        temp[first] = source[first];
    }
}