Recursion

While trying to stay sharp with my coding skills, after graduating from Flatiron School Software Engineering program, I have stumbled into many kinds of coding problems at leetcode like implementing any Tree traversals, getting the branch sums in a binary tree, etc … All of them are problems I solved using recursion, so I decided to write about it and deepen my understanding on recursion.

In coding, a recursive function is a function that calls itself either directly or indirectly during its execution. Recursion is about solving a problem in terms of a smaller version of the problem itself until it is small enough to be solved directly.

Let’s explore this with an example and create a function that calculates the factorial of a number (!n). Having in mind that the factorial of a number is the product of itself and all the integers below it;

We can divide this function into two parts, the condition or base case, where the problem can be solved directly, and the reduction, where the problem gets reduced to a smaller version of itself.

If we were to call this function to calculate the factorial of 5 we would get a behavior similar to this.

Here we can clearly see, how the function reduces the problem to a smaller version in each call until it reaches the base case and the problem can be solved directly.

Disadvantages of using recursion

1. It tends to need greater space requirements than using iterations as each function call will remain in the stack until the base case is reached.
2. It tends to need greater time because each time the function is called, the stack grows and the final answer is returned when the base case is reached and the stack is popped completely

Advantages of recursion

1. It tends to be more elegant than the iterative approach.
2. Recursion adds clarity and reduces the time needed to write and debug code.