Recursion & Recursive Solution

Recursion can be very hard to understand and very easy and fun to implement. It took me quite a long to really get the whole recursive process of problem solving. Let’s dig deep into the recursion and recursive way of problem-solving.

Recursion is an algorithmic technique where a function, in order to accomplish a task, calls itself with some part of the task. A recursive function calls itself on a simpler version of the problem in an attempt to simplify the problem to a point where it can be solved. With this smaller problem solved, it can work backwards to solve each slightly larger problem until the entire problem has been solved.

You can solve many complex problems using recursion easily if you can find the base case and recursive pattern of the problem.

How does recursion work?

A recursive algorithm must call itself, recursively. A recursive algorithm must have a base case. A recursive algorithm must change its state and move toward the base case

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

The recursion continues until some condition is met to prevent it.

To prevent infinite recursion, if…else statement (or similar approach) can be used where one branch makes the recursive call, and the other doesn’t.

As usual, we will try to understand recursion by solving common recursive problems.

problem

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. that is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Recursive solution

This problem can be solved using recursion as it has a base case and a recursive pattern. The base is, that it will always return 0 if n == 0 and 1 if n == 1. and we need the sum of the two preceding numbers for every n.

int fib(int n) {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        return fib(n-1) + fib(n-2);
    }

Find GCD of two numbers using recursion

GCD – greatest common divisor of two given numbers can be found using recursion with just a few lines of code.

int gcd(int num1, int num2) {
    if (num2 != 0)
        return gcd(num2, num1 % num2);
    else
        return num1;
}

The base case for finding gcd is if the number2 becomes 0 then the gcd must be number1. So our focus is to make the number2 0. We can do that by calling gcd(num2, num1%num2); You can get a real-time idea upon looking at the above image and code.

Another common example of recursion is Tree traversing. A tree has root node and two child node left and right and those child nodes can have their own child nodes and so on. To traverse a tree, recursion is the easiest way.

void TreeTraverse(TreeNode* root)
 {
    if(!root)
      return;
    cout<<root->val;
    if(root->left)
      TreeTraverse(root->left);
    if(root->right)
      TreeTraverse(root->right);
 }

when to use recursion over iteration.

Recursion is made for solving problems that can be broken down into smaller, repetitive problems and has a base case where function ultimately breaks. It is especially good for working on things that have many possible branches and are too complex for an iterative approach. Some problems are inherently recursive, such as Graph and Tree Traversal.

Here is a list of problems you can solve using recursion.

Advantages and Disadvantages of Recursion

Recursion makes the program elegant. However, if performance is vital, use loops instead as recursion is usually much slower.

For a recursive function, you only need to define the base case and recursive case, so the code is simpler and shorter than an iterative code. It is an important concept. It is frequently used in data structures and algorithms. For example, it is common to use recursion in problems such as tree traversal.

Here are some blogs for beginners to begin with programming. Programming And Problem Solving, Programming And The Ad Hoc Problems. Till then happy coding 😊