Recursion

For solving problems with a naturally repeating structure - they are defined in terms of themselves.

Structure of a recursive function:

1. One or more base cases - usually the smallest input.

2. One or more ways of reducing the problem and then solving the smaller problem using recursion.

3. One or more ways of using the solution to each smaller problem to solve our large problem.

Verify that a recursive function is correct:

1. Verify the base cases:

   • are they correct?

   • are they exhaustive? (Will I reach them?)

2. Harness the power of functional abstraction:

   1. Assume that factorial(n-1) is correct.

   2. Verify that factorial(n) is correct.

Identifying patterns:

1. List out all cases.

2. Identify patterns between each case.

3. Simplify repeated code with recursive call.

Tree Recursion

• a function that makes multiple recursive calls is a tree recursive function.