Recursion

Keywords and Basic Problems

Recursion — is a phenomenon when a function calls itself until a specific condition is met.

If the condition is not met, if the program is running infinitely, it will lead to overflowing of the Stack leading to Segmentation fault. This situation is called Stack Overflow. The Space where the functions are yet to be completed are placed is called the Stack Space.

The condition where the recursive function stops is called the Base Condition / Base Case and the pictorial representation of relations that shows the tree of the recursive calls is called a Recursion Tree.

Some Basic Problems

1. Print Name N times using Recursion —

class Main {
    public static void main(String[] args) {
        name("Name", 5);
    }
    public static void name(String s, int n) {
        if(n == 0){
            return;
        }
        System.out.println(s);
        name(s, n-1);
    }
}

TC: O(N)
SC: O(N) — internally it uses the Stack space

2. Print 1 to N using recursion —

class Main {
    public static void main(String[] args) {
        count(1, 5);
    }
    public static void count(int i, int n) {
        // int i = 1;
        if(i > n){
            return;
        }
        System.out.print(i);
        System.out.print(" ");
        count(i+1, n);
    }
}

TC: O(N)
SC: O(N)

3. Print N to 1 using recursion —

class Main {
    public static void main(String[] args) {
        count(5);
    }
    public static void count(int n) {
        // int i = 1;
        if(n == 0){
            return;
        }
        System.out.print(n);
        System.out.print(" ");
        count(n-1);
    }
}

TC: O(N)
SC: O(N)

4. Sum of first N numbers —

class Main {
    public static void main(String[] args) {
        int ans = sum(5);
        System.out.println(ans);
    }
    public static int sum(int n) {
        if(n == 0){
            return 0;
        }
       return n + sum(n-1);
    }
}

TC: O(N)
SC: O(N)

5. Reverse an array —

class Main {
    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5};
        print(arr, arr.length-1);
    }
    public static void print(int arr[], int n) {
        if(n < 0) {
            return;
        }
        System.out.print(arr[n] + " ");
        print(arr, n-1);
    }
}

TC: O(N)
SC: O(N)

These are a few basic questions that you come across while solving recursion when in an interview.

Keywords: Recursion, Base Case, Condition, Recursion Tree, Segmentation Fault, Stack Space, Stack Overflow.