Definition

Recursion is the property of defining a function in terms of itself.

Mathematical Recursion Examples

• Factorial: N! = N * (N - 1)!
• Exponentiation: a^n = a * a^(n-1)
• Arithmetic sequence: a_n = a_(n-1) + r
• Fibonacci sequence: F_n = F_(n-1) + F_(n-2)
• Greatest Common Divisor (GCD): gcd(a, b) = gcd(b, a % b) if b > 0, else a
• Sum of digits: sumDigits(n) = n % 10 + sumDigits(n / 10)
• Number of digits: numDigits(n) = 1 + numDigits(n / 10) if n >= 10
• Maximum digit: maxDigit(n) = max(n % 10, maxDigit(n / 10))

Types of Recursion

• Direct recursion: A function F calls itself.
• Indirect recursion: A function F calls function G, which in turn calls F.

Factorial Function in Java

Iterative Approach

public class Factorial {
    public static int fact(int n) {
        int p = 1;
        for (int i = 1; i <= n; i++) {
            p *= i;
        }
        return p;
    }
    public static void main(String[] args) {
        int result = fact(5);
        System.out.println("Factorial: " + result);
    }
}
        

Recursive Approach

public class Factorial {
    public static int fact(int n) {
        if (n == 0)
            return 1;
        else
            return n * fact(n - 1);
    }
    public static void main(String[] args) {
        int result = fact(5);
        System.out.println("Factorial: " + result);
    }
}
        

Stack Execution in Recursion

Each recursive function call adds a new memory zone in the stack until it reaches the base case.

Example: Recursive Combinations Function

public class Combinations {
    public static int comb(int n, int k) {
        if (n == k || k == 0)
            return 1;
        else
            return comb(n - 1, k - 1) + comb(n - 1, k);
    }
    public static void main(String[] args) {
        System.out.println(comb(5, 2));
    }
}
        

Recursive Call Execution

Each recursive function maintains its local variables separately on the stack. A function call will continue until it reaches the base case.

Key Observations in Recursion

• A recursive function must include a base case to prevent infinite recursion.
• Parameter values in recursive calls should move towards the base case.

How to Implement Recursive Calls?

• If a recursive function returns a value, the recursive call is placed in an expression.
• If a recursive function is void, the recursive call is a standalone statement.

Example of a Void Recursive Function

public class Factorial {
    public static void fact(int n, int[] r) {
        if (n == 0)
            r[0] = 1;
        else {
            fact(n - 1, r);
            r[0] *= n;
        }
    }
    public static void main(String[] args) {
        int[] a = new int[1];
        fact(4, a);
        System.out.println(a[0]);
    }
}
        

Example of a Non-Void Recursive Function

public class Factorial {
    public static int fact(int n) {
        int result;
        if (n == 0)
            result = 1;
        else
            result = fact(n - 1) * n;
        return result;
    }
    public static void main(String[] args) {
        int x = fact(3);
        System.out.println("Factorial of 3: " + x);
    }
}