Algorithm Problem Solving — Recursion basics
We are going to talk about how to intuitively think about recursion.
Problem Statement
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 step(s). In how many distinct ways you can climb to the top?
This problem is a typical model for recursion. To easily visualize how you can solve this problem assume that you are on the top position already, A friend of yours is going to climb up the stairs.
As you started observing this you would have probably identified the pattern, your friend can make the decision of taking either 1 step or 2 steps from the current position. Assume your friend is in Stair #X and if he/she decides to take 1 step from there that will be one distinct route and if he/she decides to take 2 steps from there that will be another distinct route. The problem states asks us to account for all the routes and thus we should basically do this at every step.
To add more visualization to this problem, assume that your friend has 5 steps left to climb. Let’s see the number of ways in which he/she can do it.
I have highlighted one of the distinct ways to get to the top where the friend took the combination of 2+2+1 to reach the top, the other paths are intentionally left incomplete, but you can very well observe that decision at every point will uniquely generate and path.
Implementation:
I have added conditions in the code to handle the edge cases in an elegant way, I would highly encourage as an exercise to walk through the example to understand why the conditions work the way they do.
Optimization:
Clearly we are doing some duplicate calculations here as you see in the recursion tree the number 3,2, 1 are repeated multiple times and it can be resolved using a technique called Memoization. My next post would be to adding optimization to this problem.
Additional problem:
Try applying the thinking to the following problem.
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.Given N, calculate F(N).
