Steps to Write a Recursive Program

Writing a Recursive Program

We learned through examples how recursive programs work. Now, let me explain the step by step process which I follow to think about the problems recursively. By following the steps below, and with enough practice, you can think recursively too.

Step 1:  Think about the smallest problem to solve

Whenever you encounter a problem, think about the base case first. Ask yourself – What’s the smallest problem I can solve without the need to call the function? The key is to return the result as soon as the base case condition is satisfied.

Step 2:  Try writing the formula for solving the big problem in terms of the smaller problem

If possible, then write the problem. We did the same for the two problems we discussed – Factorial and Fibonacci. Factorial of n was calculated by multiplying n by the result of the factorial of n-1. The key is to not worry about how the small problem will be solved. This is the beauty of recursion. The function will keep calling itself until the base case is reached, and then the magic happens. If you have doubts in your mind whether your program will work as intended, try to visualize the implementation on a piece of paper. But there is no need to draw the stack diagram. You can verify the correctness of the program using the method which we saw while discussing the Fibonacci program–the recursive tree method. 

By following the above steps, you will also start thinking recursively 😉