Algorithm | Recursion Function

Recursion Function

A recursive function is a function that calls itself again during processing.
For example, a function that calculates the sum from 1 to N can be defined with recursion as follows.

public class SumRecursion {

    public int sum(int n) {
        if(n == 0) {
            return 0;
        }
        return n + sum(n - 1);
    }

    public static void main(String[] args) {
        SumRecursion recursion = new SumRecursion();
        int result = recursion.sum(10);
        System.out.println(result); // 55
    }
}

Execution result:

One thing to note is that although sum(10) is called, the first value returned is from sum(0). Finally, the value of sum(10) is returned.

Euclidean Algorithm

The Euclidean algorithm is an algorithm for finding the greatest common divisor(GCD(m, n)) of two integers m and n.

When m is divided by n and the remainder is r, it is defined as follows.

GCD(m, n) = GCD(n, r)

Using a recursive function, you can write the well-known Euclidean algorithm.

public class GcdRecursion {

    public int gcd(int m, int n) {
        if(n == 0) {
            return m;
        }
        return gcd(n,  m % n);
    }

    public static void main(String[] args) {
        GcdRecursion recursion = new GcdRecursion();
        int result = recursion.gcd(30, 7);
        System.out.println(result); // 1
    }
}

Execution result:

Fibonacci Sequence

The Fibonacci sequence algorithm can be made using recursion twice and is defined as follows.

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 (n = 2, 3, ...)

public class FibonacciRecursion {
    
    public int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        FibonacciRecursion recursion = new FibonacciRecursion();
        int result = recursion.fibonacci(10);
        System.out.println(result); // 55
    }
}

Execution result:

The complexity of the Fibonacci algorithm written above is O((1+√5)^n/2).

Calculating the Sum from a to b

The code below is an example that calculates the sum from a to b.

package com.devkuma.algorithum.programming.recursion;

public class SumRangeRecursion {

    int sumRange(int a, int b) {
        if (a == b) {
            return a;
        }
        return sumRange(a, b - 1) + b;
    }

    public static void main(String[] args) {
        SumRangeRecursion recursion = new SumRangeRecursion();
        int result = recursion.sumRange(1, 3);
        System.out.println(result); // 6
    }
}

Execution result:

In the example above, the calculation proceeds like 1 + 2 + 3 + 4 + 5 = 15.

Written out, it looks like this.

sumRange(1, 5) = sumRange(1, 5 - 1) + 5 > sumRange(1, 4) + 5 > 10 + 5 = 15
sumRange(1, 4) = sumRange(1, 4 - 1) + 4 > sumRange(1, 3) + 4 > 6 + 4 = 10
sumRange(1, 3) = sumRange(1, 3 - 1) + 3 > sumRange(1, 2) + 3 > 3 + 3 = 6
sumRange(1, 2) = sumRange(1, 2 - 1) + 2 > sumRange(1, 1) + 2 > 1 + 2 = 3
sumRange(1, 1) = 1

Determining Whether a Number Is Prime

The code below is an example that determines whether a number is prime.

public class PrimeRecursion {

    boolean hasDivisor(int n, int i) {
        if (i == n) {
            return false;
        }
        if (n % i == 0) {
            return true;
        }
        return hasDivisor(n, i + 1);
    }

    boolean isPrime(int n) {
        if (n == 1) {
            return false;
        } else if (n == 2) {
            return true;
        } else {
            return !hasDivisor(n, 2);
        }
    }

    public static void main(String[] args) {
        PrimeRecursion recursion = new PrimeRecursion();
        boolean result1 = recursion.isPrime(7);
        System.out.println(result1); // true

        boolean result2 = recursion.isPrime(4);
        System.out.println(result2); // false
    }

}

Execution result:

true
false

Mutual Recursion: Determining Odd and Even

The code below is an example that determines odd and even numbers using mutual recursive functions where methods call each other.

package com.devkuma.algorithum.programming.recursion;

public class EvenOddRecursion {

    boolean isEven(int n) {
        if (n == 0) {
            return true;
        }
        return isOdd(n-1);
    }

    boolean isOdd(int n) {
        if (n == 0) {
            return false;
        }
        return isEven(n-1);
    }

    public static void main(String[] args) {
        EvenOddRecursion recursion = new EvenOddRecursion();

        System.out.println(recursion.isEven(8)); // true
        System.out.println(recursion.isEven(9)); // false
        System.out.println(recursion.isOdd(8)); // false
        System.out.println(recursion.isOdd(9)); // true
    }
}

Execution result:

true
false
false
true

Finding the Maximum Value in an Array

The code below is an example that finds the maximum value up to count n in the input array a.

public class MaxArrayRecursion {

    public static int max(int[] a, int n) {
        int x;
        if (n == 1) {
            return a[0];
        } else {
            x = max(a, n - 1);
        }

        if (x > a[n - 1]) {
            return x;
        }
        return a[n - 1];
    }

    public static void main(String[] args) {
        int arr[] = {0, 80, 60, 40, 20, 100};
        System.out.println(max(arr, 3));
    }
}

Execution result:

Up to the third element of the input array a is “0, 80, 60”, and the largest value among them is “80”.