A function calls by itself is known as direct recursion.
All recursive algorithms must obey three important laws:
Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller sub-problems 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):
Topics covered in this snack-sized chapter:
- Often more "elegant” and concise than a loop.
Recursion should be considered when:
- Sometimes very inefficient.
- 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).
Sometimes the "work" of the algorithm is done after the base case is reached.
- Reducing the problem size leads to the base case.
- 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.
if (answer is known) provide the answer.
make a recursive call to solve a smaller version of the same problem
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 * (N-1)!
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.