Basic Recursion Examples in Java

Main.java

import java.util.Scanner;

public class Recursion {
    /**
     * 计算 n 的阶乘
     * @param n 非负整数
     * @return n 的阶乘
     */
    private static int factorial(int n) {
        if (n == 0) { // 如果 n 是 0，说明算到阶乘的最后一步了，直接返回 1（递归的终止条件）
            return 1;
        } else {
            return n * factorial(n - 1); // 否则，返回 n 乘以 n - 1 的阶乘，这样就可以递归地计算 n 的阶乘
        }
    }

    /**
     * 计算 n 的 m 次方
     * @param n 底数
     * @param m 指数
     * @return n 的 m 次方
     */
    private static double power(double n, double m) {
        if (m == 0) { // 如果 m 是 0，说明算到幂的最后一步了，直接返回 1（递归的终止条件）
            return 1;
        } else {
            if (m < 0) { // 如果 m 是负数，说明是求 n 的负 m 次方
                // 使用公式 n^(-m) = 1 / (n^m) 来计算 n 的负 m 次方
                return 1/(n * power(n, Math.abs(m) - 1)); // 这里使用了 Math.abs 方法来获取 m 的绝对值，来算 n 的 m 次方，然后再取倒数
            } else {
                return n * power(n, m - 1); // 否则，返回 n 乘以 n 的 m - 1 次方，这样就可以递归地计算 n 的 m 次方
            }
        }
    }

    /**
     * 计算 1 + 2 + 3 + ... + n 的和
     * @param n 非负整数
     * @return 1 + 2 + 3 + ... + n 的和
     */
    private static int sum(int n) {
        if (n == 0) { // 如果 n 是 0，说明算到和的最后一步了，直接返回 0（递归的终止条件）
            return 0;
        } else {
            return n + sum(n - 1); // 否则，返回 n 加上 1 + 2 + 3 + ... + (n - 1) 的和，这样就可以递归地计算 1 + 2 + 3 + ... + n 的和
        }
    }

    /**
     * 计算斐波那契数列的第 n 项
     * @param n 非负整数
     * @return 斐波那契数列的第 n 项
     */
    private static int fibonacci(int n) {
        if (n == 0 || n == 1) { // 如果 n 是 0 或 1，说明算到斐波那契数列的最后一步了，直接返回 n（递归的终止条件）
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2); // 否则，返回第 n - 1 项加上第 n - 2 项，这样就可以递归地计算斐波那契数列的第 n 项
        }
    }

    /**
     * 判断一个数是否是质数
     * @param n 要判断的数
     * @param f 从 2 开始的因子
     * @return 是否是质数
     */
    private static boolean isPrime(int n, int f) {
        if (n == f) { // 如果 n 等于 f，说明已经判断完了所有可能的因子，返回 true（递归的终止条件），这个数是质数
            return true;
        }
        if (n % f == 0) { // 如果 n 还没有等于 f 就已经可以被 f 整除，说明 n 不是质数，返回 false
            return false;
        }
        return isPrime(n, f + 1); // 否则还需要继续判断下一个因子
    }

    /**
     * 输出 n 到 100 之间的所有质数
     * @param n 起始数
     */
    private static void prime(int n) {
        if (n != 100) { // 如果 n 不等于 100，说明还没有到 100，继续判断
            if (isPrime(n, 2)) { // 如果 n 是质数
                System.out.print(n + " "); // 输出 n
            }
            prime(n + 1); // 继续判断下一个数
        }
    }

    /**
     * 将一个十进制数转换为二进制
     * @param num 十进制数
     * @param result 目前的结果
     * @return 二进制数
     */
    private static String toBase(int num, String result) {
        if (num == 0) { // 如果 num 是 0，说明已经转换完了，返回结果
            return result;
        } else { // 否则
            int remainder = num % 2; // 求余数，当前数除2的余数就是二进制数的当前位
            return toBase(num / 2, remainder + result); // 递归地将 num 除以 2，余数加到结果的前面，然后继续求下一位二进制数
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
//        System.out.print("Enter a number: ");
//        int n = scanner.nextInt();
//        System.out.println(sum(n));
//        System.out.println(fibonacci(n));
//        prime(3);
        System.out.print("Enter decimal to convert: ");
        int num = scanner.nextInt();
        System.out.print("Enter base to convert to: ");
        int base = scanner.nextInt();
        System.out.println(toBase(num, ""));
    }
}