,
Share On

Claps upto fifty times for each post.

27


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;
}
gcd recursive process

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 😊


One response to “Recursion & Recursive Solution”

  1. […] them when needed later. In case you want to get clear about recursion first just go through this blog beforehand. This is part one of the dynamic programming blog […]

Leave a Reply

Your email address will not be published. Required fields are marked *

AKM Elias Avatar

Click to follow this author!

4 Followers


Posts by this author

Share your local WordPress site.

24 February 2024

Dynamic programming! A blog generated by ChatGPT

08 December 2022

Dynamic programming part – 1(Memoization)

30 October 2022

Recursion & Recursive Solution

12 September 2022

Programming and The Ad Hoc problems.

28 August 2022


Posts related this

Dynamic programming! A blog generated by ChatGPT

AKM Elias

08 December 2022

Dynamic programming part – 1(Memoization)

AKM Elias

30 October 2022

Recursion & Recursive Solution

AKM Elias

12 September 2022

Programming and The Ad Hoc problems.

AKM Elias

28 August 2022

Programming and problem solving

AKM Elias

21 August 2022