An Introduction to Recursion
Hello readers! You must have heard of Recursion. It is an important concept for programming — be it competitive or academic as well as for technical interviews. This article will give you an introduction to recursion.
Note: There is no prerequisite to learning this concept but knowing functions and a little bit of any programming language. To read briefly about functions click here.
So what exactly is recursion?
a) Function calling itself
b) Until base case is satisfied
So, a part of recursion implies a case/situation in which a function calls itself.
In the above sample code, the main function call on line 10 calls itself, which in turn calls the function() on line 6 and again calls the function() on line 6 and so on.
The following diagram depicts how the program executes:
But, there is a problem in the above scenario. The output 1 keeps on printing without any bounds, leading to infinite recursion or StackOverflow.
We all understand when a program complies, some memory (in terms of stack) is allocated to the program. However, when the computer program, like in this case, tries to use more memory space in the called stack than allocated, leads to overflow often termed as StackOverflow.
This brings us to the next point in defining recursion, which states that function calls are made until a specific condition/criterion is met. This condition is also known as the BASE CASE (Base Condition).
Let’s now transform the above sample by including a base case, i.e. printing 1 until the counter reaches the value of 3.
Let’s understand how the program executes when recursive calls are made to the function f(), with the base condition as “until the counter is 3”.
The above diagram is very similar to how memory space (stack) is consumed when a recursive program executes.
To simplify function calls depiction, Recursive Trees are used. They are hence a convenient way to represent the process of recursive calls pictorially.
For our above example, the following recursion tree can be used.
- Recursion is a concept that involves any arbitrary function calling itself until the base case is reached.
- StackOverflow occurs when infinite recursion occurs, i.e. base case is not specified during the function definition.
- A Recursion Tree is a pictorial way to depict recursive program execution.
Thanks for reading! Do subscribe and share with everyone in your community and don’t forget to like and comment. Follow my Medium Page Rishika Gupta.