Introduction to Recursion

Algorithms and data structures are the fundamental building blocks of computer science. Most real-world problems can be modeled and solved using algorithms and data structures. In this tutorial, we are going to go over one such algorithmic technique named recursion. We are also going to explore various coding interview problems that can be solved using recursion. <!--more-->

Table of contents #

1. Prerequisites

2. Understanding Recursion

3. Fibonacci Numbers

4. Factorial

5. Pros And Cons Of Recursion

6. Conclusion

Prerequisites #

1. Basic understanding of Programming.

2. Basic knowledge of Python.

Understanding Recursion #

According to Wikipedia, in computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Recursion falls under a category of algorithms called "divide and conquer", in which a problem is broken down into smaller sub-problems that are easier to solve.

These subproblems are solved individually, and the final result is the culmination of these results of all these subproblems. In other words, if you write a function that performs a certain task by calling itself, the function is called a recursive function, and this process is called recursion.

Note: Google the word "recursion" and Google will display: "Did you mean: recursion". When you click on the link, it'll take you to the same page. This is a clever example of how recursion works.

Let us look at a mathematical interpretation:

f(x) is a function defined as: f(x) = f(x - 1) +f(x - 2)

This is called a Fibonacci function, and the numbers generated by this function are called the Fibonacci numbers. The first term is 1, the second term is also 1, but the third term and every other term henceforth follow the rule defined above. In other words, every term is the sum of the previous two terms.

The numbers are 1, 1, 2, 3, 5, 8, 13, and so on. This is an elegant example of a recursive function in which it calls itself with a different argument. Let's understand this better by coding it in Python.

Fibonacci numbers #

We are going to write a program to return the "n"th Fibonacci number. For example, the 5th Fibonacci number is 5, and the 7th is 13. Our function will take one argument: n(the term we wish to calculate)

def fibonacci(n):

	if(n == 1 or n == 2):

		return 1
	  
	return fibonacci(n - 1) + fibonacci(n - 2)
  
n = int(input('Enter the nth term: '))

print(fibonacci(n))

The (n == 1 or n == 2) condition in the function is called a "terminating condition". It is essential for every recursive function, as a function without this condition will keep calling itself and never terminate (infinite loop causes the program to crash). We know that the first two terms are 1, so we can return 1 when n is 1 or 2.

This is also called a "base case" or a "base condition", and is usually something that we already know. For instance, we might know the answer for n = 0 or some other specific value of n. If we know this "base" value, we can use it to calculate all the other values.

Factorial #

A factorial is a mathematical expression that most students would have come across. The factorial of a number is defined as the product of all positive integers less than or equal to that number. In other words, if n is a positive integer, the factorial of n will be:

factorial(n) = n * (n - 1) * (n - 2) * ........... * (3) * (2) * (1)

For example,

factorial(4) = 4 * 3 * 2 * 1 = 24

factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

factorial(6) = 6 * 5 * 4 * 3 * 2 * 1 = 720

factorial(1) = 1 * 1 = 1

One interesting pattern that we observe here is that the factorial of 'n' is equal to n multiplied by factorial(n - 1). In other words, factorial(5) = 5 * factorial(4). Similarly, factorial(6) = 6 * factorial(5). In general, factorial(n) = n * factorial(n - 1). Interestingly, this looks exactly like a recursive function in which we call the factorial function multiple times with different arguments. We know that factorial(1) = 1, which will be the terminating condition for our function.

Note: An important rule in mathematics is that the factorial of 0 is 1. In other words, factorial(0) = 1. We are going to use this as the base case of our function.

Code:

def factorial(n):

	if(n == 0 or n == 1):

		return 1

	return n * factorial(n - 1)

n = int(input('Enter the number: '))

print(factorial(n))

In the function above, the terminating condition, as stated before, is: (n == 0 or n == 1). We return 1 since factorial(1) = factorial(0) = 1. Otherwise, we use the formula described above to calculate the factorial when n is greater than 1.

Pros and cons of Recursion #

Pros:

• It is intuitive: Recursion is easier to understand since a recursive function is similar to functions in mathematics. Some functions such as the Fibonacci and factorial are inherently recursive and easier to code.

Cons:

• It is not efficient in terms of memory: Since recursion involves function calls, each recursive call creates an entry for all the variables and constants in the function stack. These values are kept there until the function returns. Therefore, recursion is always limited by the stack space in the system. If a recursive function requires more memory than what is available in the stack, a common and prevalent error called stack overflow occurs. Check out this article for more details.

• It is not fast: Iteration (using loops) is faster than recursion because every time a function is called, there is an overhead of allocating space for the function and all its data in the function stack. This causes a slight delay in recursive functions when compared to iteration. This StackOverflow question is a good read on the function call stack and how it works.

Conclusion #

In this article, we reviewed how recursion works and looked at a few interesting problems. Recursion is an intuitive algorithmic technique, as a wide array of problems are inherently recursive and can be solved by dividing the problem into smaller subproblems. However, recursion is not the most efficient or most optimal technique and has its flaws.

Fortunately, there are many ways to overcome this hurdle and solve problems optimally by consuming less time and less memory. One such technique is called dynamic programming and will be discussed in the next article. You can head over to Hackerrank and practice a wide array of problems on recursion. Hackerrank allows you to select the difficulty level of the problems, making it ideal for beginners.

---

Peer Review Contributions by: Mohan Raj