Brief Introduction to Recursion

Tusamma Sal Sabil
Mar 16, 2020 · 7 min read

What is recursion?

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

A physical world example would be to place two parallel mirrors facing each other. Any object in between them would be reflected recursively.

Using recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Fibonacci Series, nCr, Factorial etc.

Types of Recursions:

  1. Tail Recursion: If a recursive function calling itself and that recursive call is the last statement in the function then it’s known as Tail Recursion. After that call the recursive function performs nothing. The function has to process or perform any operation at the time of calling and it does nothing at returning time.
  2. Head Recursion: If a recursive function calling itself and that recursive call is the first statement in the function then it’s known as Head Recursion. There’s no statement, no operation before the call. The function doesn’t have to process or perform any operation at the time of calling and all operations are done at returning time.
  3. Tree Recursion: To understand Tree Recursion let’s first understand Linear Recursion. If a recursive function calling itself for one time then it’s known as Linear Recursion. Otherwise if a recursive function calling itself for more than one time then it’s known as Tree Recursion.
  4. Indirect Recursion: In this recursion, there may be more than one functions and they are calling one another in a circular manner.
  5. Nested Recursion: In this recursion, a recursive function will pass the parameter as a recursive call.That means “recursion inside recursion”. Let see the example to understand this recursion.

Will add details discussion in next parts.

Let’s take a simple recursive function now and analyze its space and time complexity.

def func(n):
if n > 1:
return func(n-1)

Let’s do the time complexity analysis first. Assume that the total time taken for the above function func() is T(n). Now the T(n) is a sum of the time taken to compare if n is greater than 1 and the time taken to execute func(n-1). So, T(n) can be expressed as -

T(n) = 1 + T(n−1)

1 is the time taken for the comparison (you can put any constant there). Now, what will be the time (in terms of T(n)) for executing func(n-1)?

T(n−1) = 1 + T(n−2)

Similarly,

T(n−2) = 1 + T(n−3)

and so on.

If you pay close attention to the equations, they all are connected. Aren’t they? If you substitute them after one another, you get -

T(n) = 1 + (1 + T(n−2)) = 2 + T(n−2) = 3 + T(n−3) = …. = k + T(n−k) (after running the function for k terms)

Now, you need to determine at what point the function is going to stop. According to the anchor condition given, you can write -

Assume that, after running for k terms, the function stops running. If so, then it must be -

n − k = 1 => k = n−1

Now substituting the value of k (= n -1) in T(n)=k+T(n−k) :

T(n) = (n−1) + T(n−(n−1))

=> T(n) = (n−1)+T(1)

=> T(n) = n−1+1 = n # For T(1) only comparison is required

By the rule of time complexity analysis, T(n)=n can be rewritten as T(n)=O(n). This means the time complexity (worst) of the function is O(n).

The space complexity analysis of the function is simple. The function is an in-memory function and does not make use of any extra variables. So, you can conclude that the space complexity of the function O(n).

Python Recursive Function

We know that in Python, a function can call other functions. It is even possible for the function to call itself. These type of construct are termed as recursive functions.

Following is an example of recursive function to find the factorial of an integer.

Factorial of a number is the product of all the integers from 1 to that number. For example, the factorial of 6 (denoted as 6!) is 1*2*3*4*5*6 = 720.

How recursion works?

def factorial(n):
if n == 1:
return 1
else:
return (n * factorial(n-1))
num = 5print("The factorial of", num, "is", factorial(num))

In the above example, factorial() is a recursive functions as it calls itself.

When we call this function with a positive integer, it will recursively call itself by decreasing the number.

Each function call multiples the number with the factorial of number 1 until the number is equal to one. This recursive call can be explained in the following steps.

factorial(5)                  # 1st call with 5
5 * factorial(4) # 2nd call with 4
5 * 4 * factorial(3) # 3rd call with 3
5 * 4 * 3 * factorial(2) # 4th call with 2
5 * 4 * 3 * 2 * factorial(1) # 5th call with 1
5 * 4 * 3 * 2 * 1 # return from 5th call as number=1
5 * 4 * 3 * 2 # return from 4th call
5 * 4 * 6 # return from 3rd call
5 * 24 # return from 2nd call
120 # return from 1st call

Our recursion ends when the number reduces to 1. This is called the base condition.

Every recursive function must have a base condition that stops the recursion or else the function calls itself infinitely.

What is a base case in recursion

When working with recursion, we should define a base case for which we already know the answer. In the above example we are finding factorial of an integer number and we already know that the factorial of 1 is 1 so this is our base case.

Let’s go through another easy example,

def print_number(n):
if n > 0:
print(n)
print_number(n-1)
num = 3print_number(num)

Steps:

  1. It call print_number function with n = 3 as print_number(3). If check if n is greater than 0. Yes 3 is greater than 0 so it print 3 and call print_number function again with n = n — 1.
  2. It call print_number function with n = 2 as print_number(2). If check if n is greater than 0. Yes 2 is greater than 0 so it print 2 and call print_number function again with n = n — 1.
  3. It call print_number function with n = 1 as print_number(1). If check if n is greater than 0. Yes 1 is greater than 0 so it print 1 and call print_number function again with n = n — 1.
  4. It call print_number function with n = 0 as print_number(1). If check if n is greater than 0. No 0 is not greater than 0 so it ends the execution of print_number function.

Please follow the below tracing tree for better understanding:

How Recursion uses Stack?

For above example let’s discuss how this function use stack memory.

When print_number(3) executes it’s create a record in stack memory. Similarly it creates record for print_number(2), print_number(1) and print_number(0). After reaching base condition point it starts returning values and deleting records those actions are finished.

See below mentioned chart for better understanding.

Space-time analysis of a recursive function:

For a given input, a function is supposed to produce some kind of output. In order to do that how much time does the function takes? The time-complexity measure approximates this time, and it is also called the runtime of the function. Similarly, the space-complexity measure approximates the space (memory) requirements of a function, i.e., for a given input. But why these are even required?

  • Instead of running a function on the range of inputs with varying sizes, you can easily approximate how a function might behave on different inputs with varying sizes.
  • If you have two functions that are fulfilling the same objective which one will you take? What measures will you consider to make the decision? Yes, you guessed it right. You will compare them by analyzing their space and time complexities and see which one is performing better.

Advantages of Recursion

  1. Easier to write.
  2. Code is easier to read and understand.
  3. Recursive functions make the code look clean and elegant.
  4. A complex task can be broken down into simpler sub-problems using recursion.
  5. Sequence generation is easier with recursion than using some nested iteration.
  6. It takes less lines of code to solve a problem using recursion.

Disadvantages of Recursion

  1. Not all problems can be solved using recursion.
  2. If you don’t define the base case then the code would run indefinitely.
  3. Sometimes the logic behind recursion is hard to follow through.
  4. Recursive calls are expensive (inefficient) as they take up a lot of memory and time.
  5. Recursive functions are hard to debug.

GitHub Link: Recursion Introduction

Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data…

Sign up for Analytics Vidhya News Bytes

By Analytics Vidhya

Latest news from Analytics Vidhya on our Hackathons and some of our best articles! Take a look

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Tusamma Sal Sabil

Written by

I love to explore and share knowledge. My GitHub Repo: https://github.com/tssovi/ and Linkedin: https://www.linkedin.com/in/tssovi/

Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data Science professionals. We are building the next-gen data science ecosystem https://www.analyticsvidhya.com

Tusamma Sal Sabil

Written by

I love to explore and share knowledge. My GitHub Repo: https://github.com/tssovi/ and Linkedin: https://www.linkedin.com/in/tssovi/

Analytics Vidhya

Analytics Vidhya is a community of Analytics and Data Science professionals. We are building the next-gen data science ecosystem https://www.analyticsvidhya.com

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

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