Mastering Recursion for Beginners [Part 1]
Recursion is a challenging but fundamental topic for programmers to master. The first time I encountered recursion, I was overwhelmed and intrigued by how a function calling itself with a base condition could solve complex problems. It took me a while to understand the concept, but I eventually came to appreciate its power and elegance.
Taking with an basic example of calculating factorial of a number.
Most people start by focusing on the base case, which is not wrong. However, finding the transition state is much better. To do this, you need to think about the recurrence relation and draw a recursion tree.
For example n=3;
3!=3*2*1=6 Right!
In recursion, we assume that we can get the factorial of a subproblem by some means. This is a leap of faith, but it works. The leap of faith is that we assume that the factorial of the sub-problem can be computed by some means, even though we don’t know how to do it. But if we can compute the factorial of the sub-problem, then we can compute the factorial of the original problem.
We want to find 3! but we somehow get the value of 2!. So to get 3!, we simply do 3 * 2!. For number n, the relation is f(n) = n * f(n — 1). Assume that the function call to the subproblem will give you the right answer. Now we can think of a base case like if n == 1, then we simply return 1.
I am gonna explain few more examples in my next articles so you get better understanding recursion.
