Recursion Practice Problems

1. Print the word “GFG” n times using recursion.

class Solution {

    void printGfg(int N) {
        if (N < 1) return;

        printGfg(N - 1);
        System.out.print("GFG ");
    }
}

2. Print the numbers from n to 1 using recursion.

def more(n):
    if n < 1: # base case
        return
    print(n) # print n first to do it in decrementing order
    more(n - 1)

more(3)

3. Print the sum of the first n numbers. For instance, when n = 3…the first 3 numbers sum to 6…therefore 1 + 2 + 3 = 6. There are two ways to solve this problem, one using parameterized recursion and the other using functional recursion.

Parameterized way (a function with parameters):

function(i, sum){
    if (i < 1){ // base case
        print(sum);
        return;
    }
    function(i - 1, sum + 1);
}

Assuming the function call was function(3, 0), we go through the function, the base case does not execute, and the recursive function executes with function(2, 1), this function calls another function, and as time goes on, the value of i keeps decrementing by 1 as the value of sum keeps incrementing by 1. It goes on until our base case is reached, and then we print the sum.

Functional way (using a direct recursive function):

function(n){
    if (n == 0){
        return 0;
    }
    return n + function(n - 1);
}

Same thing, if this function is called with function(3), the base case does not execute, and the recursive function executes with 3 + function(2), which calls another function, all the way until it reaches the base case. When the base case gets executed, it returns a value 0, that 0, replaces the last recursive call that met the base case i.e return 1 + function(0), becomes return 1 + 0 and this goes up the recursion tree until it reaches the first function. Then the value gets returned.

This idea can be extended to find the factorial of a number where factorial(3) = 1 * 2 * 3. It’s the same idea as the above, just that it’s multiplication instead of addition. And the base case will change, because if our base case returns 0, the overall product becomes 0 as well since everything multiplied by 0 is 0:

factorial(n){
    if (n == 0){
        return 1;
    }
    return n * factorial(n - 1);
}