How, why, and when is recursion the better choice for your algorithm?
Recursion is an algorithm design technique in which the underlying algorithm calls itself with updated input until certain conditions are met. These terminating conditions that end the recursive call of the algorithm are also called "the base" of the recursion. How can a process (aka algorithm) can actually call itself? Simple. All there is to know is that there exist a dependence relationship between the states of the algorithm. For example, consider the famous Fibonacci sequence of natural numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, etc. One can notice that each term of that sequence, except the first two, can be writen as a sum of the previous two terms. In other words there exist the following dependence relationship between the current state and the previous two states: 1 1 2 = 1 + 1 3 = 2 + 1 5 = 3 + 2 8 = 5 + 3 13 = 8 + 5 21 = 13 + 8 The formal way to write this relationship between the terms is: f(n) = f(...