Recursion

     Recursion is a process that repeats itself until it reaches a solution. The solution to a recursive problem requires the solution to a smaller version of the same problem. A recursive algorithm has a Base Case (a case that the solution is known for), as well as a Recursive Step (which determines how the recursion should repeat itself and make use of smaller cases). For example, in order to find the "n"th Fibonacci number, F(n), we need to find F(n-1) and F(n-2) because the recursive step for Fibonacci numbers is, F(n) = F(n-1) + F(n-2). Similarly, in order to find F(n-1), we need to first find F(n-2) and F(n-3).We repeat this process until we reach our base cases, F(1) and F(2). It is known that F(1) = F(2) = 1. From the base case, we can determine that F(3) = 2, F(4) = 3, and ...

     Another example is the Sierpinski triangle. The picture below demonstrates that in each step, we take a black triangle and we turn it into 3 black triangles with 1 white triangle in the middle.

Advantages:

• If implemented well, recursion can be a great solution to some problems.
• Using recursion can reduce the amount of code written.
• There are some problems that simply cannot be solved without recursion. For example, in order to display all the files in a system, you need to use recursion.