Recursion

What is Recursion?

   Recursion is an algorithmic method for solving problems where the problem itself consists of a number of sub-problems that are near identical, but smaller to itself. These sub-problems, however, must eventually reach a base case.( Else we just end up trying to solve an infinite number of sub-problems which will probably just end up in the process's stack space being exhausted ) Since the method involves solving similar, smaller sub-problems, it shouldn't be surprising that recursion involves a function calling itself with modified arguments.

1. Recursion involves solving a problem by solving similar but smaller sub-problems.
2. There must be a base case, so at some point, the decomposition of problems into sub-problems will stop.
3. Recursive solutions to problems involve functions calling themselves with modified arguments.

Note: This isn't the only situation in which recursion is applicable and this isn't the only way to think about recursion. In my opinion, this is just the best way to introduce the concept.

   Finding the nth number of the Fibonacci sequence is an easy way to demonstrate how recursion works. Since recursion involves solving a problem by solving similar sub-problems, then it would seem logical that the function would call itself.


 In the Fibonacci sequence, each term is the result of the sum of the previous two terms. The exception to this would be the first two terms where they are both 1.


 Let's say we wanted to find the nth number of the Fibonacci sequence. If n was 1 or 2, then we would just return the number, 1. However, if n > 2, then we would return the sum of the two previous fibonacci numbers, Fib(n-1) and Fib(n-2).


Fib(n) is the original problem. We find it's solution by solving similar, smaller sub-problems, Fib(n-1) and Fib(n-2).


In this code snippet, we can clearly see all the characteristics of a recursive solution.

1. The problem of finding the nth Fibonacci number is computed using the solutions to similar sub-problems;  Fib(n-1), Fib(n-2)
2. The base case exists when n=1,2 for Fib(n)
3. The Fib function indeed does call itself with modified arguments.