Javarevisited
Published in

Javarevisited

What is Recursion and How does it Work?

Have you all while watching a code in any programming language observed where a function being defined is applied within its own definition? and maybe you just have ignored that, aah! it’s just the function call what is that something I have to do with?

Well, this is one of the most important concepts in programming, basically when you talk about mathematics and computer science, in which a function calls itself directly or indirectly or a function being defined is applied within its own definition.

Now, most of us have written code that involves writing recursive functions, but before writing a well defined recursive function we will need to keep in mind the following two conditions which are very important, which are:

  1. The Base Case for our function, recursive functions apparently defines an infinite number of function calls, so to end the function call at some step you will need a base case for the same!

You might have heard of the Fibonacci Sequence, which is one of the best examples of recursion

Fib(0) = 0 as base case 1
Fib(1) = 1 as base case 2
For all integers n > 1, Fib(n) = Fib(n − 1) + Fib(n − 2)

Now, let’s take a look and understand how recursion works, although it’s easy to look into recursive functions and write down codes for solving various algorithmic problems, have you ever tried to understand it and see how it actually works behind the screen, and how you can make necessary changes to manipulate you function to perform something more than just stated? well, if not then don’t worry! I will make your work easy and help you understand how it actually works by taking an example of the Pre-Order traversal of a Binary Tree!

Now, before jumping to our code and understanding more about recursion, let’s take a look at a new term that is recursion stack or the call stack

Definition:

The Call Stack is something very similar to what we all might have used in solving various algorithmic problems, that is Stack, we all know, that it uses the LIFO rule to perform functions, which stands for “Last In First Out”, where you add things one after another and take off the most recently added item from it! Before moving to the Pre-Order traversal, let’s know, what is preorder traversal?

Definition:

Pre-Order traversal is a way of traversing in a binary tree where we start from the root node and traverse through the left child nodes of the parent node at each level and then to its right child.

Algorithm:
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)

Code For Preorder Traversal

Now, let's have a look at the code:

void preorderTraversal(struct node* node){if (node == NULL)
return;
/* first print data of node */
cout << node->val << " ";
/* recursion performed on left subtree */
preorderTraversal(node->left);
/* now perform recursion on right subtree */
preorderTraversal(node->right);
}

Now, let’s have a look at the Pre-Order traversal of a Binary Tree and understand how recursion works!

Fig 0.0: A Binary Tree

Now, we have a given binary tree as shown above!

Fig 1.1

Now, in the first step, we have a binary tree on the left-hand side and a call stack on the right-hand side, now the pointer points to the root node as shown, we move to the root node’s left child and push the root to our call stack

Fig 2.2

In the second step, we pushed the current node into the call stack and move to its left child node

Fig 3.3

In the third step, we pushed the current last left node to the stack and move to its left child node

Fig: 4.4

In the fourth step, we can observe that there is neither a left child nor the right child of 20, so we will pop out the current node and recursively move to the code line preorderTraversal(node->right) where node 10’s right child is pushed to our call stack, i.e. 25 is pushed into the call stack.

Fig 5.5

In the next pre final step, since we have no left or the right child of 25, we will pop out the current node and recursively move back to the root node’s right child node 15 and push it into the call stack, and pop out root node 5 from the call stack.

Fig 6.6

In the final step we see that again, there are no left and the right child of node 15, so we pop out the current node and get the output as shown in the above diagram, which is our final output.

So, you can easily understand how recursion works, there are many more examples of recursion, I have tried to explain it in an easy way by taking a complex problem that many students face while writing the code for binary trees.

Keep learning and keep growing and also keep exploring more!

All the very best!

For more interesting and informative articles and tips follow me on Medium and Linkedin

--

--

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
Swapnil Kant

Hi, I am Swapnil Kant, an avid programmer, and a full-time learner! One who is highly interested in Algorithm Optimization and Development