## Recursion

Sometimes solving a big problem may require us to solve smaller problems of similar nature. For example, computing the xth number in the fibonacci sequence may require us to find the x-1th and the x-2th numbers in the sequence. If we are able to break the main problem into smaller instances of the same problem again and again, so that eventually the smaller problems become trivial, then we can use the solutions to the trivial problems to progressively build bigger solutions. Consequently, we can reach the solution of our main problem. This concept when used in coding is called recursion.

For writing a recursive code for a problem, we simply call a function inside the definition of the same function. Thus the definition of GNU (the source of much free software) is said to be recursive because GNU stands for 'GNU's Not Unix', i.e. GNU is part of the definition of GNU! Or maybe two mirrors placed parallely! The nested images are a form of infinite recursion.