# 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:

- 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! - The
**Recursive Step**Now, to reach the base case you will need a**recursive step**which will eventually lead to the**base case**and terminate the process.

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:

voidpreorderTraversal(structnode* 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!

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

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**

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

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

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

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

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**