Recursion and the Leap of Faith

In this article, we are going to discuss how we can solve any iterative problem using recursion with three standard steps and the concept of recursive Leap of Faith.

Recursion is one of those concepts which is familiar to all but used by few.
We all know the formal definition of recursion that was taught us in schools :

• When a method calls itself that method is known as a recursive method.

In real life, however, we rarely come across any recursive methods. Most programmers prefer to use iteration over Recursion and it might be difficult to get our head around a recursive method but once understood it can make our code a lot less redundant.

Let’s look at some code to see recursive ways of doing things.

Sum of first n whole numbers using recursion.

Sum of first n whole numbers using the iterative method.

As we can see the recursive method is much more concise

Sum of n whole numbers using Recursion in three steps:

1. Write a base condition.
2. Find a pattern or common relation on the sequence.
3. Write a general solution.

1. Base Condition:

A base condition is a simplest possible input for a given problem.

When finding the sum of the simplest possible input must be zero because the sum of 0 is 0.

I.e. Sum(0) =0 no further calculation needed.

That’s it! We will write down the base condition first.

Let’s check the code.

As we can see the base condition is concluded, since n is 0 the sum of zero numbers is n itself ( Sum(0) = 0 )

2. Finding a pattern in the sequence

So to solve any recursive problem, a bigger problem is converted into smaller problems.

In this step we try to answer a single question: can we find the sum of any number if the next number’s sum is provided to us.

Like here in this case.

If we have sum(2) then we can find the sum(3) as

Sum (3) = sum(2)+1

Similarly sum(9) = sum(8)+1

sum(1) = sum(0)+1

So now we know how to find the sum of a number if the sum of the number next in sequence is given to us.

3. Writing a general solution

From the second step, we can conclude the general solution is

sum of n whole numbers = sum(n-1)+1

Let’s write down the resulting final code.

So what we have done here is that if the value of n is 1 replace it with 1.

Here we will assume that sum of any number n is n+sum(n-1) even if we do not know the value of sum(n-1). This is called the recursive leap of Faith. The reason why it is called a leap of faith is that we assume to know the value of addNumber(n-1)

By using the same three steps and two lines we can solve every recursive problem

How does recursion work:

There are two phases in which any recursive problem is solved:

1. Every new method created is pushed onto a stack till the base condition is met.
2. After the base condition is met all the methods are solved one by one till the stack is empty and the final value is considered as the answer

If the base condition is not correctly defined it can fill up the stack giving us a stack overflow error.

Advantages of recursion over Iterative approach:

1. Reduces code size and increases readability.
2. Can make the code faster in some cases.
3. Better for tree traversing.

Drawbacks

1. Recursion takes up more space: It has the Space complexity of O(n), which means that n objects will be created for stack space using recursion compared to O(1) constant space complexity when using loops.
2. Can cause Stack Overflow if not used correctly.