【java数据结构与算法学习】几个递归算法的实现

比眉伴天荒 2022-05-30 05:17 242阅读 0赞

这次刚看到递归，写了几个递归的算法。其中包含了求阶乘、斐波那契数列、字符串逆序输出、折半查找实现。

import java.io.IOException;
    import java.util.Scanner;
    
    public class Recuse {
        //n的阶乘
        public int jieCheng(int n){
            //n的阶乘 = n * n-1的阶乘
            if (n == 1){
                return 1;
            }
            return jieCheng(n-1) * n;
        }
        //斐波那契：前两个数相加等于后一个数
        public int feiBoNaQie(int n){
            if ( n == 1){return 1;}
            if ( n == 2){return 1;}
            return feiBoNaQie(n - 1) + feiBoNaQie(n - 2);
        }
        //输入字符串逆序
        public void reverseString(String s) {
            //递归终止条件
            if ("".equals(s)){
                return;
            }
            //利用递归回溯的原理
            reverseString(s.substring(1,s.length()));
            System.out.print(s.substring(0,1));
        }
        //折半查找(循环)
        public int halfFind(int[] array, int search){
            int low = 0;
            int height = array.length;
            int mid = (low + height) /2;
    
            while (low <= height){
                if (search > array[mid]){
                    low = mid + 1;
                }else if(search < array[mid]){
                    height = mid - 1;
                }else{
                    return mid;
                }
                mid = (low + height) /2;
            }
            return -1;
        }
        //折半查找(递归)
        public int halfFindByResursive(int[] array, int low, int height, int search){
            int mid = (low + height)/2;
            //没找到
            if (low > height){
                return -1;
            }
            //如果查找的值大于中间值，查右边
            if (array[mid] < search){
                return halfFindByResursive(array , mid+1, height, search);
                //小于中间值，查左边
            }else if (array[mid] > search){
                return halfFindByResursive(array , low, mid-1, search);
            }else {
                //找到了
                return mid;
            }
        }
    
        public static void main(String[] args) throws IOException {
            Recuse recuse = new Recuse();
            //阶乘
            System.out.println(recuse.jieCheng(5));
            //斐波那契
            for (int i = 1;i<=20;i++){
                System.out.println(recuse.feiBoNaQie(i));
            }
            //反转输入字符
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            recuse.reverseString(s);
            System.out.println();
            //折半查找
            int[] arr = {2,6,9,33,75,91,262,356};
            int i = recuse.halfFind(arr, 2);
            System.out.println(i);
            //折半查找（递归）
            int index = recuse.halfFindByResursive(arr, 0, arr.length, 1);
            System.out.println(index);
        }
    }