Geek Culture
Published in

Geek Culture

An Introduction to Recursion

An Introduction to Recursion
Photo by Max Harlynking on Unsplash

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.

Sample Code for Recursion

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:

Recursive Calls to f()

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.

Sample Code for Recursion

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”.

Recursive calls to function f() with the counter condition

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 Tree Example

Let’s summarize:

  • 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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Rishika Gupta

Rishika Gupta

64 Followers

Senior Developer. Computer Engineer. | Writing: Python, Programming & Bioinformatics | Let’s connect via LinkedIn — rishika_g