[数据结构与算法]基础）Note18）初识递归

上学的时候老师说人理解循环，神理解递归。递归在排序算法中经常能看到。

一，什么是递归

??递归就是方法自己调用自己，所有的循环都可以改写为递归，但是递归并不一定能改写为循环。

二，递归的实现

package com.hzc.recursion;

/**
 * @author flowerWorm
 * @createTime 2021年10月22日 20:58:00
 */
public class RecursionDemo01 {
    /**
     * 何为递归?递归就是方法自己调用自己,所有的循环都可以改写为递归,但是递归未必能改写成为循环.
     * 求1+2+3+...+100
     */
    public static void main(String[] args) {
        System.out.println(byFor(100));//循环的方式解5050
        System.out.println(byRecursion(100));//用递归的方式解5050
    }

    public static Long byFor(int n){
        Long l = 0L;
        for (int i=1; i<=n; i++){
            l = l + i;
        }
        return l;
    }

    public static Long byRecursion(int n){
        if (n == 1){
            return 1L;//递归结束条件
        }else {
            return byRecursion(n-1) + n;
        }
    }
}

三，递归的实现（求数组最大值）

package com.hzc.recursion;

import java.util.Arrays;

/**
 * @author flowerWorm
 * @createTime 2021年10月22日 20:58:00
 */
public class RecursionDemo02 {
    /**
     * 何为递归?递归就是方法自己调用自己,所有的循环都可以改写为递归,但是递归未必能改写成为循环.
     * 求数组中最大值
     */
    public static void main(String[] args) {
        int[] arr = new int[]{1,3,4,6,88,34,100,7,2};
        System.out.println(byFor(arr));//循环的方式解100
        System.out.println(byRecursion(arr, 0, arr.length-1));//用递归的方式解100
    }

    public static int byFor(int[] arr){
        int max = 0;
        for (int i=0; i<arr.length; i++){
            if (arr[i] > max){
                max = arr[i];
            }
        }
        return max;
    }

    /**
     * 求数组最大值
     * @param arr 指定数组
     * @param l 左边界,第一个数
     * @param r 右边界,数组的长度
     * @return
     */
    public static int byRecursion(int[] arr, int l, int r){
        if (l == r){
            return arr[l];
        }else {
            int a = arr[l];
            /*
            这里运用递归的思想将数组的第一个元素与其他元素先视为两个整体,
            然后用递归的方法求出后面部分的最大值,然后跟第一个数比较即可
             */
            int b = byRecursion(arr, l+1, r);
            if (a > b){
                return a;
            }else {
                return b;
            }
        }
    }
}

四，递归的实现（斐波那契数列）

package com.hzc.recursion;

/**
 * @author flowerWorm
 * @createTime 2021年10月22日 20:58:00
 */
public class RecursionDemo03 {
    /**
     * 何为递归?递归就是方法自己调用自己,所有的循环都可以改写为递归,但是递归未必能改写成为循环.
     * 斐波那契数列 1, 1, 2, 3, 5, 8, 13, 21 ..., n
     */
    public static void main(String[] args) {
        System.out.println(byRecursion(20));//用递归的方式解100
    }

    public static int byRecursion(int n){
        if (n == 1){
            return 1;
        }else if (n == 2){
            return 1;
        }
        return (byRecursion(n-1) + byRecursion(n-2));
    }
}