Recursion

 

Recursion

Introduction to Recursion: Grasping Recursion by Repeating an Action N Times

Pre-requisite: The learner must know how to write a basic function in any language and how to make a function call from the main function.

What is Recursion?

Recursion is a process in which a function invokes or call itself repeatedly until a certain condition is met.

Let’s understand recursion with the help of an illustration:

 

As illustrated above, a function invokes or call itself within its own definition.   Without a stopping condition, these recursive calls will continue indefinitely, eventually leading to a stack overflow when the memory limit is exceeded.

What is Stack Overflow in Recursion?

Whenever recursion calls are executed, they’re simultaneously stored in a recursion stack where they wait for the completion of the recursive function. A recursive function can only be completed if a base condition is fulfilled and the control returns to the parent function. 

But, when there is no base condition given for a particular recursive function, it gets called indefinitely which results in a Stack Overflow i.e, exceeding the memory limit of the recursion stack and hence the program terminates giving a Segmentation Fault error. 

The illustration above also represents the case of a Stack Overflow as there is no terminating condition for recursion to stop, hence it will also result in a memory limit exceeded error.

Base Condition

A base condition is a crucial component of a recursive function that prevents it from running indefinitely. It defines the specific scenario in which the function should terminate and return control to its parent function. When the base condition is met, the recursion stops.

To better understand the importance of a base condition in recursive functions, let’s consider an example:

Example: Printing Integers from 0 to 2

Here’s how the pseudocode for this task might look:

function printNumbers(n): 

 if n > 2: // Base condition 

 return print(n) // Print the current number 

 printNumbers(n + 1) // Recursive call with incremented value

 // Main function 

printNumbers(0) // Start the recursion with 0

Recursive code for printing numbers from 0 to 3 : 

CODE  

#include <bits/stdc++.h>
using namespace std;
int cnt = 0;

void print(){
   
   // Base Condition.
   if(cnt == 3)  return;
   cout<<cnt<<endl;

   // Count Incremented
   cnt++;
   print();

}

int main(){
    print();
  return 0;
}

Recursive Tree

A recursive tree is a visual representation that illustrates the structure of recursive function calls. Each node in the tree represents a function call, while the edges indicate the relationships between calls.

When a recursive call finishes executing, control returns to the parent function, which then continues its execution. 

As a summary of the lecture, the basics of recursion such as the following were clear to us : 

• What is Recursion
• Base Condition
• Stack Overflow / Stack Space
• Recursion Tree