Recursion

To understand recursion, one first understand recursion.

Table of Contents

  • Introduction
  • What is Recursion
  • Why is Recursion tricky to understand?
  • Problem Solving using Recursion
    • Find nth Fibonacci number
    • Find Factorial of n
    • Reverse a string
    • Sum of numbers in an array
    • Binary Search
    • Sort an array (i.e. vector in C++) of integers using Merge Sort
    • Print the post-order traversal of a binary tree
    • Print the Depth First Traversal of a graph
  • Takeaway
  • Writing a Recursive Code
  • Tail Recursion
  • Finally

Introduction

If you struggle a bit with recursion, let me first tell you that you are not alone. The human mind can sometimes behave irrationally. Sometimes it can’t grasp anything even after a lot of information, but a simple visual element can make it understand the most complex concepts. Maybe that’s why they say “A picture is worth 1000 words”.

In this blog post, I am making an attempt to explain the process of recursion in detail and I hope that you don’t ever need to revisit the concept again. I am also going to solve some problems based on recursion so that the theory meets practical coding as well. Wasting no time, let’s dive in.

What is Recursion?

Formally, as you might already know, recursion is a process when a function calls itself directly or indirectly. 

What do I mean by directly? Something like this –

void fun(int x) {
// ....
fun(x-1);
// ....
}

What do I mean by indirectly? Something like this –

int fun1(int x) {
// ....
fun2(x-1);
// ....
}
int fun2(int x) {
// ....
fun1(x-1);
// ....
}

Here, fun1() calls fun2() which in turn calls fun1(). This means that fun1() indirectly calls itself.

Why is Recursion tricky to understand?

When a function calls another function, we can easily imagine the execution going into the other function and coming back to the calling function once the called function is executed completely. It’s a “visual” process.

However, when it comes to recursion, it’s difficult to visualize the execution sequence.

Let’s consider an example:-

A well-known question of finding the factorial of a positive number (using recursion – for the purpose of this exercise).

Without Recursion (The way in which recursion unfolds.)

int factorial_1() {
return 1;
}
int factorial_2() {
int fact_1 = factorial_1();
return 2 * fact_1;
}
int factorial_3() {
int fact_2 = factorial_2();
return 3 * fact_2;
}

With Recursion

int factorial(int n) {
if (n == 1) {
return 1;
}
int fact_n_1 = factorial(n-1);
return n * fact_n_1;
}
view raw FactorialOf3.cpp hosted with ❤ by GitHub

Main

int main() {
int non_recursive_factorial_3 = factorial3();
int recursive_factorial_3 = factorial(3);
return 0;
}

Although both ways return the correct result, one way is clearly easy to visualize than the other.

The execution sequence for non-recursive code would be (line numbers) :
10, 11, 5, 6, 1, 2, 3, 7, 8, 12, 13.

While the same for recursive code would be:
1, 2, 5, 1, 2, 5, 1, 2, 3, 4, 5, 6, 7, 5, 6, 7.

For the ease of visualization, I have colored the execution sequence differently. Orange is when n is 3, Green is when n is 2, and Blue is when n is 1.

The fact that I had to use colors to explain to you the execution sequence – is the real pain point behind understanding recursion. It’s not very visual.

You understood why you were struggling with recursion, now let’s get into the part where you don’t have to struggle anymore.

The key behind understanding recursive code or writing the recursive code is to NOT visualize it. What you should do instead is to ASSUME. Assume that the recursive call will give you whatever you want. Assume that it will give you the correct result. What will you do with that result is the next thing you should be thinking of.

Going back to our example of factorial. The recursive code we have written, barely does anything. At line 5, we assume that we will get the correct answer whatever it is. In this case, we assume that it will give us the answer of factorial of n-1. Next thing we need to think of is, what will we do with the factorial of n-1. We know that factorial of number n is n multiplied by factorial of n-1. So that’s exactly what we did and returned the value. And this is where our function finished.

The only thing that we did not talk about yet is when to stop assuming and doing the actual work. As you can see, line 5 and line 6 barely do any real work. Line 5 assumed it would get the answer for factorial of n-1 and line 6 capitalized on that. Somebody has to do the real hard work and that is where the base condition comes into picture. When we call the factorial(3) from the main() function, the line 5 of factorial(3) assumes factorial(2) to give the answer. Similarly, line 5 of factorial(2) assumes factorial(1) to give the answer. If we don’t stop this “assuming”, it would just keep going on indefinitely. We know that the factorial of 1 is 1. So instead of taking the route of assuming factorial(0) will give the answer, factorial(1) does the actual work of returning the answer. In general, base cases are exactly for doing the real work. We write “Base case” relying on what we already know. For the factorial problem, we know that factorial of 1 is 1. So we used that as the base condition and developed a general factorial of n function.

Problem Solving using Recursion

The above way of thinking doesn’t just work on factorial, it works on all recursive codes. Let’s take another simple example before diving into complex one’s. 

Find nth Fibonacci number

  1. Assumption part
    nth Fibonacci number is the sum of (n-1)th Fibonacci number and (n-2)th Fibonacci number
  2. Base case (What we already know?)
    The 1st number is 0 and the 2nd number is 1.

Let’s develop the code for finding the general  nth Fibonacci number.

int fibonacci(int n) {
if (n == 1) {
return 0;
}
if (n == 2) {
return 1;
}
int n_minus_1_fibonacci = fibonacci(n-1);
int n_minus_2_fibonacci = fibonacci(n-2);
return n_minus_1_fibonacci + n_minus_2_fibonacci;
}

Lines 2 – 7 are part of the base case.
Lines 8 – 9 are part of our assumption.
Line 10 does what needs to be done if we get what we want after the assumption. In this case it is adding the two previous values.

Putting our earlier example in the same framework –

Find Factorial of n

  1. Assumption part
    n factorial is multiplication of n and (n-1) factorial.
  2. Base case (What we already know?)
    Factorial of 1 is 1.

Let’s develop the code for finding n factorial.

int factorial(int n) {
if (n == 1) {
return 1;
}
int fact_n_1 = factorial(n-1);
return n * fact_n_1;
}

Lines 2 – 4 are part of the base case.
Line 5 is a part of our assumption.
Line 6 does what needs to be done if we get the answer for n-1 factorial. In this case, it is multiplying that value with n.

Let’s move to the next problem of reversing a string.

Reverse a string

  1. Assume 
    To reverse the entire string, swap the first and last character and reverse the middle part.
  1. Base case
    If the size of the string is 1 or 0, then we don’t need to do anything because the reversed string is going to be the same.

Let’s develop the recursive code for reversing the string.

string reverse(string s) {
int length = s.size();
if (length <= 1) {
return s;
}
string middle_part = string(s.begin()+1, s.end()-1);
string reversed_middle_part = reverse(middle_part);
string first_char = string(s.begin(), s.begin()+1);
string last_char = string(s.end()-1, s.end());
string reversed = last_char + reversed_middle_part + first_char;
return reversed;
}

Line 3 – 5 –> Base case
Line 8 –> Assumption
Line 10 – 13 –> What to do if the recursive call returns the correct answer? In this case, move last character to front, front character to last and insert the reversed middle part in the middle.

Let’s take a look at how we can find the sum of all numbers in the array using recursion.

Sum of numbers in an array

(Return sum of all numbers in the array).

  1. Assume
    Excluding the current element, the sum of other numbers can be calculated.
  1. Base case
    If there is only one element left in the array, the sum is equal to the element.

Let’s develop the recursive code for adding all numbers together.

int sum_of_array(vector<int> nums, int start_index, int end_index) {
if (start_index == end_index) {
return nums[start_index];
}
int sum = sum_of_array(nums, start_index+1, end_index);
return sum + nums[start_index];
}

Lines 2 – 4 are part of the base case.
Line 5 is a part of our assumption.
Line 6 does what needs to be done if we get the answer for the sum of remaining numbers in the array. In this case, add the current value into the sum.

Similarly, you can find the maximum in the array as : 

int max_in_array(vector<int> nums, int start_index, int end_index) {
if (start_index == end_index) {
return nums[start_index];
}
int maximum = max_in_array(nums, start_index+1, end_index);
return max(nums[start_index], maximum);
}

So far we saw very simple examples and you might have already solved the above problems either recursively or iteratively. Also, the above examples were a bit far stretched just so that I can demonstrate the use of recursion. We will now see some common problems that are generally implemented recursively.

Let’s take a look at binary search.

Binary Search

(Here we will only return a boolean value, whether the number K exists or not).

  1. Assume
    The binary-search on the left half or the right half part will check whether the number K exists or not.
  2. Base case
    1. If the middle element is what we were looking for i.e. K, then return true.
    2. If the low has gone beyond high, then we didn’t find the element.

Let’s develop the recursive code for binary search.

bool binary_search(vector<int> sorted_nums, int low, int high, int K) {
if (low > high) {
return false;
}
int mid = (low+high)/2;
if (sorted_nums[mid] == K) {
return true;
}
bool is_found = false;
if (sorted_nums[mid] < K) {
is_found = binary_search(sorted_nums, mid + 1, high, K);
} else {
is_found = binary_search(sorted_nums, low, mid - 1, K);
}
return is_found;
}

Line 2 – 9 –> Base case. (Yes, sometimes it is a bit long, but it’s always just what we already know, so not hard).
Line 13 & 15 –> Assumption.
Line 18 –> Do what is needed. In this case, just return the status.

Next Problem – Merge Sort.

Sort an array (i.e. vector in C++) of integers using Merge Sort

  1. Assume
    (Merge-)Sorting of the left half and the right half will be correct.
  2. Base Condition
    As an array of size 1 or 0 is always sorted, return it as is.

(Remember that Merge sort uses a merge() method to merge two sorted arrays. Here we will not implement that. However, we will only pass the sorted arrays to it. We will focus on the recursive part of the merge sort here.)

Let’s develop the code for merge sort recursively.

vector<int> merge_sort(vector<int> nums) {
int length = nums.size();
if (length <= 1) {
return numbers;
}
int half = length/2;
vector<int> left_half = vector<int>(nums.begin(), nums.begin()+half);
vector<int> right_half = vector<int>(nums.begin()+half, nums.end());
vector<int> sorted_left = merge_sort(left_half);
vector<int> sorted_right = merge_sort(right_half);
vector<int> sorted_full = merge(sorted_left, sorted_right);
return sorted_full;
}

Line 3 – 5 –> Base case
Line 10 – 11 –> Assumption
Line 13 – 14 –> Do what needs to be done. In this case, merge the two sorted arrays.

Print the post-order traversal of a binary tree

  1. Assume
    1. Print the post-order traversal of the left subtree.
    2. Print the post-order traversal of the right subtree.
    3. Display the value of the root.
  2. Base case
    Post-order traversal of an empty tree is empty.

Let’s develop the code for printing the post-order traversal recursively.

void print_post_order_traversal(TreeNode *root) {
if (root == nullptr) {
return;
}
print_post_order_traversal(root->left);
print_post_order_traversal(root->right);
print(root->value);
}

Line 2 – 4 –> Base case
Line 5 – 6 –> Assumption
Line 7 –> Do what needs to be done. In this case, it’s just printing the value of the current root. Printing of left and right parts is already taken care of (remember, the assumption).

Next.

Print the Depth First Traversal of a graph

  1. Assume
    Printing of Depth first traversal of the neighbors will be correct.
  2. Base case
    If the current node is already visited, we don’t need to visit it again. So once visited, keep the record that it’s visited.

Let’s develop the code for printing depth first traversal.

void print_depth_first_traversal(GraphNode *node) {
if (is_visited(node)) {
return;
}
mark_visited(node);
for (GraphNode *neighbor : node->neighbors) {
print_depth_first_traversal(neighbor);
}
print(node->value);
}

Line 2 – 4 –> Base case. Line 5 supports correct working of the base case.
Line 7 – 9 –> Assumption. They assume that the depth first traversal of all neighbors will be correct.
Line 11 –> Do what needs to be done. In this case, just print.

Takeaway

I hope that the examples above helped you in getting the understanding of how to think about recursion. I also believe that you must have found it easy to understand. 

Although you might have noticed already, there are always 3 parts in a recursive code.

  1. Base Case
    This is what actually stops the recursion. If the base case is incorrect or not present at all, expect your program to throw the runtime error because of stack overflow, memory limit exceeded.
  2. General case
    This is the assumption part where we call the same function with different parameter values)
  3. Using the result provided by recursive call or some steps that we need to do in addition to calling recursively.
    In the case of fibonacci, we added the previous two values; for factorial, we multiplied the result with the current value; for the sum of the array, we added the current number to the result; for max in the array, we found the maximum between the current number and the result.

Writing a Recursive Code

Now, if you were able to get a good understanding so far, the above 3 steps should also guide you to write a recursive code on your own for the problem at hand. For any problem, I like to solve the problem on paper first and then shift to the computer. For recursive problem, I like to write in mathematical form like –

For Factorial:

F(x)  = 1 ______________________ For 0 <= x <= 1 
      = x * F(x-1) _____________ Otherwise.

For Fibonacci:

F(x) = 0 _______________________ For x = 1
     = 1 _______________________ For x = 2
     = F(x-1) + F(x-2) _________ Otherwise

This is an easy way to write it on paper and it’s easy to convert this into code too. For any problem, you should think if recursion would make it easy to solve it. Can the problem be solved by dividing it?

  1. Sometimes a bigger problem can be solved by getting an answer to a relatively smaller problem.
    E.g. Factorial of n can be solved by finding the factorial of n-1, Fibonacci of n can be calculated from fibonacci of n-1 and n-2, Sum of n can be found using sum of n-1, etc.
  2. Sometimes a bigger problem can be solved by solving a collection of smaller problems.
    E.g. Array of size n can be sorted by using Merge sort by dividing it into 2 arrays of size n/2, printing the depth first traversal of graph is solved by printing depth first traversals of all the neighbors.

So in general, wherever you can reduce the problem of size n into a smaller problem or collection of smaller problems, you can use recursion as long as the problem is the same and the only difference is in size. What I mean by that is, although it’s obvious, you can not solve a factorial of n problem using a fibonacci problem of smaller size. ‘Factorial of n’ problem can only be solved using factorial problems of smaller size.

With some practice, you are now on a path to get better at writing recursive codes and understand the recursion better. 

Tail Recursion

I also wanted to cover a small concept of “tail recursion”.

Tail recursion is, obviously, a recursion in which a recursive call to the  function is the last statement of the function body. 

E.g. 

int fun(int n) {
// ...
return fun(n-1);
}

The last statement is the only recursive call in the above function, so it is an example of tail recursion.

The reason why it is a special concept is because of the internal working of tail recursion. In general, you know that when a function is called, the stack pointer is updated, the execution starts in the called method and after finishing the execution of that method, control reaches back to the calling method using stack pointer. In case of a tail recursion, there is nothing to be done after a recursive call is made. So there is no need of coming back to the calling method once the execution is over. Hence, the compiler may try to optimize there. That’s it.

Finally

Knowing recursion opens the doors to understanding of some relatively advanced concepts like backtracking and dynamic programming. We will get to those concepts in the next couple of blog posts.  This is it for now on the topic of recursion. I would be curious to know how you feel about recursion, your thoughts on this post, and if I missed anything. Let me know in the comments below.

Of course, don’t forget to like, share the post and subscribe to the blog.

Happy Coding!

Related Posts


One thought on “Recursion

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s