Exemplos de algoritmos recursivos simples

Recursão

    /**
     * Máximo Divisor Comum recursivo
     * @param a
     * @param b
     * @return O MDC de a e b
     */
    public static int mdc(int a, int b) {
        if (b == 0) {
            return a;
        }
        return mdc(b, (a % b));
    }
    
    /**
     * Multiplicação por soma recursiva
     * 
     * Faz a multiplicação entre 2 números, sem usar o operador de multiplicação,
     * recursivamente
     * @param a
     * @param b
     * @return 
     */
    public static int multiplica(int a, int b) {
        if(a == 1) {
            return b;
        }
        return multiplica(a - 1, b) + b;
    }
    
    /**
     * Conta todos os números pares até n, recursivamente
     * @param n
     * @return 
     */
    public static int contaPares(int n) {
        if(n == 0 || n == 1) {
            return 1;
        }
        if(n % 2 == 0) {
            return contaPares(n - 1) + 1;
        } else {
            return contaPares(n - 1);
        }
    }
    
    /**
     * Potência recursiva
     * @param n número a ser elevado
     * @param pot grau da potência
     * @return n ^ pot
     */
    public static double potencia(int n, int pot) {
        if (pot == 1) {
            return n;
        }
        return n * potencia(n, pot - 1);
    }

    /**
     * Números de Fibonacci
     * @param n 
     * @return O número da sequencia desejado
     */
    public static int fibo(int n) {
        if (n < 2) {
            return n;
        }
        return fibo(n - 1) + fibo(n - 2);

    }

    /**
     * Definição matemática do fatorial:
     * f(x) = x * f(x-1), se x > 0;
     * f(0) = 1;
     * @param n
     * @return 
     */
    public static long fatorial(int n) {
        if (n == 0) {
            return 1;
        }
        return n * fatorial(n - 1);
    }