Description

Recursion is an approach to solve a problem using a function that calls itself as a subroutine.

To a void an infinite loop a recursive function must:

1. Simple base case (or cases) - terminating case that does not use recursion
2. Set of rules (recurrence relation) that reduce all the other cases to the base one

Unfolding Recursion

Example:

• Printing a string in reverse order

There are two important things to figure to implement a recursive function:

1. Recurrence Relation: The relation between the result of a problem and the result of its subproblems.
2. Base Case: The case where one can compute the result directly, also called the bottom case.

• Memoization
• Divide And Conquer
• Master Theorem
• Backtracking

Divide&Conquer VS. Backtracking

1. d&c often has a sole solution.
2. Each step in d&c is indispensable to build a final solution, in bt, they are often attempts.
3. In bt, we often don't know the exact/favorite path a priori.