Algorithms And Data Structures Interview Question - Recursion

One of the concepts you will come across when learning Algorithms and Data Structures is Recursion.

In the interview questions, you can perform some of the algorithmic tasks that will be given to you through recursion.

In this article, we will talk about recursions and their participation in the solution of some algorithms, and the pros, and cons of recursions.

First of all, let me tell you that recursions are not algorithms, they are just a concept used in solving algorithms. The importance of recursions in practice comes from the fact that they solve the given task by dividing it into sub-tasks.

Recursion is the process of the method (function) we write calling itself again.

Although it sounds strange at first glance, when solving several algorithmic problems, we see that the problem consists of the same sequence called by a different argument. In this case, it is appropriate to use recursions.

To clarify what we have said, let's solve the Euclidean algorithm for finding the GCD (Greatest Common Divisor) through recursion. So, in a simple form, Euclid's algorithm says that if we want to find the quotient of two numbers, we need to subtract the smaller number from the larger number until we get 0 at the end.

Example

GCD(18, 8)
18-8 = 10 // the difference is greater than the subtraction. Therefore, it will be 10-8 in the next step
10-8= 2 //difference is less than subtraction. Therefore, the next step will be 8-2
8-2 = 6
6-2 = 4
4-2=2
2-2=0// the number that ensures the acquisition of zero, ie 2 here is GCD
​​​​​​​So GCD(18, 8) = 2.

 //Greatest Common Divisor without recursion
 static int GCD(int first, int second) {
     while (first != 0 && second != 0) {
         if (first > second) first = first - second;
         else second = second - first;
     }
     return Math.Max(first, second);
 }

If we look carefully at the solution to the problem, we will see that the steps of the algorithm are repeated, but each time with different parameters.

So, if there is the same repeated step in the algorithm and the repetitions differ from each other only by arguments, then Recursion can be used.

//Greatest Common Divisor with Recursion
static int GCDWithRecursion(int first, int second) {
    //base part
    if (first == 0) return second;
    //recursion part
    if (first > second) return GCDWithRecursion(second, first - second);
    else return GCDWithRecursion(second, second - first);
}

Recursions consist of 2 parts. Using the base part or base case, we indicate the conditions under which the recursion will end. In the recursive part (Recursion part or recursion case), if the previous condition is not satisfied, the function is required to call itself again.

In the examples in this article and in recursions in general, it is imperative to write the base case. Otherwise, the recursion enters an infinite loop, creating a stackoverflow exception.

One of the questions you will be asked about algorithms in the interview is related to Factorial and Fibonacci numbers. Both of these issues can be solved recursively.

First, let's look at the factorial calculation. Factorial is the process of multiplying a number by the numbers before it. Example: 1*2*3*4*5 = 120. So the factorial of 5 is equal to 120.

The following two examples are of writing a factorial with for and while loops.

static int FactorialWithWhile(int number) {
    int sum = 1;
    while (number != 1) {
        sum = sum *= number;
        number--;
    }
    return sum;
}
static int FactorialWithFor(int number) {
    int sum = 1;
    for (int i = 1; i <= number; i++) {
        sum *= i;
    }
    return sum;
}

Now let's solve the factorial by recursion.

static int FactorialRecursion(int number) {
    //base part
    if (number == 1) return number;
    else //recursion part
        return number * FactorialRecursion(number - 1);
}

Let's explain the above example more clearly. A recursive operation works with stack memory space. So, every time a method (function) calls itself, additional stack me,mStackOverflowallocated to it, and the recursive process allocates space for the function on the stack until the base case.

After reaching the bottom (here the base case), the function starts to return the results it received backward. In our familiar example, the function returns 1 if the value of the number variable is 0 or 1. The function returns the numbers 2, 6, and 24 as shown in the figure as it steps from the bottom to the top. (1* 2 * 3 * 4) when the factorial is 5, we can get back the number 5* 24, i.e. 120. Because we wrote number * factorial(number-1). If number = 5, then 5 * factorial(4) = 5 * 24 = 120.

Another example is related to Fibonacci numbers. Fibonacci numbers are 1 1 2 3 5 8 13 21... Each number is equal to the sum of the 2 numbers before it.

Example: The number 5 above is equal to the sum of the numbers 2 and 3 before it.

Kod

static int Fibanocci(int number) {
    int num1 = 0;
    int num2 = 1;
    int num3 = 0;
    int result = 0;
    for (int i = 1; i <= number; i++) {
        num3 = num2 + num1;
        num1 = num2;
        num2 = num3;
        result = num3;
    }
    return result;
}

Now let's find the Fibonacci number by recursion.

static int FibanocciRec(int number) {
    //base part
    if (number <= 0) return 0;
    else if (number == 1) return 1;
    //recursion part
    else return FibanocciRec(number - 1) + FibanocciRec(number - 2);
}

So why didn't we just write the examples we've shown with recursion? As it is clear from the examples, I want you to know that any algorithm you write with recursion can be solved iteratively!!

Since the problem can be solved without recursion, why should we use recursion? In answer to this question, I want to say that there are both negative and positive aspects of using recursions.

Let's look at the pros of using recursions,

1. Recursions prevent code repetition, thereby saving us from rewriting the step we wrote
2. Recursions often make code more readable

Disadvantages of using recursions

1. Makes the code difficult to read for beginners
2. The extra stack requires memory space and in some cases, stackoverflow exception is thrown if the base part(base case)= is not specified correctly as multiple stacks are required to solve some issues.

When to use recursions

1. Trees in algorithms, to be able to write sorting and search algorithms more easily
2. When encountering the principle of divide and conquer in algorithms
3. Whenever Tree and Tree perform a logical algorithm
4. When breaking down each problem into subproblems, if that subproblem turns out to be a variant of the main problem that takes a different argument than the simple one