Topics covered in this snacksized chapter:
Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially.
Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.
Recursion is an alternative to iteration (loop):
 Often more "elegant” and concise than a loop.
 Sometimes very inefficient.
Recursion should be considered when:
 A problem can be defined in terms of successive smaller problems of the same type, i.e. recursively.
 Eventually the problem gets small enough that the answer is known (base case).
 Reducing the problem size leads to the base case.
Sometimes the "work" of the algorithm is done after the base case is reached.
All recursive algorithms must obey three important laws:
 A recursive algorithm must have a base case.
 A recursive algorithm must change its state and move toward the base case.
 A recursive algorithm must call itself, recursively.
Base Case
 if (answer is known) provide the answer.

Recursive Case
 make a recursive call to solve a smaller version of the same problem

A function calls by itself is known as direct recursion.
Indirect Recursion is when a function calls a second function which in turn calls the first function.
A recursive formula always uses the preceding term to define the next term of the sequence.
N!, for any positive integer N, is defined to be the product of all integers between 1 and N inclusive.
This definition can be expressed recursively as:
1! = 1
N! = N * (N1)!
The concept of the factorial is defined in terms of another factorial.
Eventually, the base case of 1! is reached.
A case in recursion, in which the answer is known when the termination for a recursive condition is to unwind back.
A case which returns to the answer which is closer.
A run time stack used for saving the frame stack of a function when every recursion or every call occurs.
It is a situation where a single recursive call is consisted by a function, and it is the final statement to be executed. It can be replaced by iteration.