Mastering Recursion | Explaining the Concept of Self-Referencing or Recursion for Efficient Problem Solving in Programming

To solve any a problem, we can have two types of approach. One is Iterative approach and the other is recursive approach. Here, we will discuss recursive approach in detail.

What is Recursion ?

So, recursion is where the function calls itself repeatedly until the stopping condition occurs also called as base condition. In other words, we can say that recursion is an algorithm that divides the problem into subproblems and makes our task easy to handle. Such a function is called a recursive function and algorithm used in this function is called as recursion.

Syntax of Recursive Function

In recursive functions, as the function calls itself repeatedly. So, if we don't have any condition to stop this self calling mechanism, then we will go into infinite state. Because every function will again call itself. And finally we wil get Stack Overflow error. We will discuss this more in next.

So, to stop this recursion after specific achievemnt, we have to apply a base condition. So, when ever we will meet our specific task, this base condition will stop our recursion and start moving the function backward to its start.

And the seond thing, we have in our recursive function is recursive statement, where call our function.

Let's Take an Example

Suppose, we want to sum all the elements in an array using recursion. Firstly, see what will be the recursive code for this problem.

Base Condition

Here, look onto the base condition. What this base condition tells ? As we know that in an array last index is always '1' less than the total size of array. So, if we have reached to the last index of array, would it logical to move next ? Of-Course, it would be senseless to move next, as we already reached at the end of the array, and also next to this we will get index out of range errors.

In this problem, we will make sure that as we reach to last index of our array, we will make no more recursive calls, instead of this we will return backward to the parent recursive function which called it. The statment return arr[Index], doing the same function, it will stop any more recursive calls to happen and return something to parent function.

Recursive Part -> Dry Run

Now, look onto the recursive part. Here we are calling the same function and making our function recursive function. Now, let's see how this is working.

Note : In recursion, the function calls are stored in a stack, and the recursive call which occured in the last will be removed firstly from stack.

Function call in main

So, when the main function calls the SumArray( ) function, it will be added to the stack. See the picture below.

Now, dry run the above example code. In the first level, we are passing array, variable size = 5 and a vairable Index = 0. Now check the base condition, here as Index(0) is less than the size(5), so the base condition is not satisfied and now we will move onto the next line. In the next line, we are calling function recursively. So before the completion of execution of this function, it called a new function with values as SumArray( arr, size = 5, Index = 1) and this function will be added in stack'top.

First Recursive Call

In this recursive function call we have arr ( which is same as preivious function ), a variable size ( also same ) and a variable Index = 1 ( previous one was 0, now it's 1 ). Now, as the function called itself again. So, start from beginning. Check the base condition, as Index(1) < Size(5-1) so base condition will not be satisfied and we will move to next line, where we are gain calling a new recursive call with parameters as SumArray( arr, size = 5, Index = 2 ). This recursive function will now added on to the top of the stack.

Second Recursive Call

In the second recursive function call we have arr ( which is same as preivious function ), a variable size ( also same ) and a variable Index = 2 ( previous one was 1, now it's 2 ). Now, as the function called itself again. So, start again from beginning. Check the base condition, as Index(2) < Size(5-1) so base condition will not be satisfied and we will move to next line, where we are gain calling a new recursive call with parameters SumArray( arr, size = 5, Index = 3 ). This recursive function will now added on to the top of the stack.

Third Recursive Call

In the 3rd recursive function call we have arr ( which is same as preivious function ), a variable size ( also same ) and a variable Index = 3 ( previous one was 2, now it's 3 ). Now, as the function called itself again. So, start again from beginning. Check the base condition, as Index(3) < Size(5-1) so base condition will not be satisfied and we will move to next line, where we are gain calling a new recursive call with parameters SumArray( arr, size = 5, Index = 4 ). This recursive function will now added on to the top of the stack.

Fourth Recursive Call

This recursive call is very important, as here we have arr ( which is same as preivious function ), a variable size ( also same ) and a variable Index = 4 ( previous one was 3, now it's 4 ). Now, as the function called itself again. So, start again from beginning. Check the base condition, as Index(4) == Size(5-1), hence the base condition satisfied. So, we will return a value which is arr[ Index ] ( From arr[1, 2, 3, 4, 5] , arr[ 4 ] will be 5 ). So, here we will return 5. As we are made return, so we will not move to the next line, hence no more recursive calls will made and we will start moving backward to parent functions which called these recursive function. Hence this recursive function will be popped out of from stack and will return value to previous function. See this scenerio in below :

Now, again the third recursive function will take this returned value which is '5', add arr[Index] and return the sum to it's parent. See the last line of function which is return arr[Index] + SumArray( ).

Now, again the second recursive function will take this returned value which is '9', add arr[Index] (Which we can see that in second recursive function call is 2) and return the sum to it's parent. See the last line of function which is return arr[Index] + SumArray( ).

Now, the first recursive function will take this returned value which is '12', add arr[Index] (Which we can see that in first recursive function call is 1) and return the sum to it's parent. See the last line of function which is return arr[Index] + SumArray( ).

Finaly, the main function will return the final output, which is the sum of arr[Index] and returned value, which is arr[0] + 14 ( returned value from 1st recursive function ). And this returned value will be the final output of our function, As nomore function calls remains, and our stack is empty, so this output is the final output.

Resources

• GitHub Repository View Problems Solved with Recursion and their Solutions and Solutions also with Arrays in this reposotory.
• DSA in CpluPlus View the GitHub Repository to check and to analyze how to complete DSA in C++
• DSA in Python If you want to continue with DSA in Python, I mentioned LeetCode Question Solved in Python using DSA.
• Lecture On Stack Implementation with Arrays You can also view my lecture on Implementation of Stack with arrays on YouTube.

#PostfixEvaluation #StackApplications #DataStructures #BackendDevelopment #ExpressionEvaluation #TechExplained #ProgrammingConcepts #ComputerScience #CodeEducation #DeveloperJourney #CodingSkills #AlgorithmicThinking #MathematicsInProgramming #SoftwareEngineering #TechEducation #DSA