- How to replace a loop with recursion?

- What is head recursion?

- What is tail recursion?

- Differences between head and tail recursion?

- Tail recursion call tree

- Head recursion call tree

## 2. Addition

- How to find base cases?

- Problem decomposition

- How to determine the size of the problem?

- Recursion diagram as a tool to design recursive programs

- What to do in the combine step?

- How to find the recursive case?

- Mathematical representation of recursive function

- How choice of reduction affects performance

- Recursive rule for efficient solution

- Translating mathematical function into recursive code

## 3. Multiplication

- How to derive recurrence relation?

- How to reassemble the result of subproblems to get the result for original problem?

- Improving the efficiency of the recursive solution

- How to determine the number of base cases?

## 4. Division

- Using a counter

- How to create a trace table

- Concrete case analysis using recursion diagram

- Reducing the problem size by more than one unit

- Recognize implicit counter in recursive code

## 5. Summation

- Expressing the problem mathematically

- Determine the size of the problem

- Using induction in the recursion diagram

- Translating recursion diagram into recursive solution

- Comparison of iterative and recursive solutions

- Recursion call stack

- Time and space complexity

- Linear recursion

## 6. Array Sum

- How data handled by base case affects recursive case

- Choosing what to reduce when you have many options

- Trace table showing the computations occurring when recursive calls terminate

## 7. Modulo

- Deriving equation to solve a problem

- Time complexity for equation based implementation

- Solving the problem by hand (brute force)

- Solving the problem by translating manual steps to iterative code

- Recognizing nothing to be done in combine step using recursion diagram

- Trivial combine step in recursion leads to tail recursion

- Comparison of iterative and recursive solution to see how terminating condition maps to base case, result and reduced value are the same in this case

## 8. Even

- Without using % operator

- Time and space complexity

- Iterative Solution

- Using multiply and divide

- Recursion diagram

- Recursive solution

- Fixing stack overflow error

- Reduction step

- Trivial combine step

- Tail recursion

- Two base cases

- How many base cases are required?

- Time and space complexity

- Linear recursion

## 9. Exponent

- Powers of 2 (warmup)

- Exponentiation operator

- Implement without using exponentiation operator

- Iterative solution

- Product accumulator

- Powers of a given base

- Recursive implementation in linear time

- Size of the problem

- Base cases

- Reduce and combine

- Allow negative integer exponents

- Problem decomposition

- Recursive case

- Relationship between reduction step and base case

- Function to express recursive case

- Multiple recursive cases

- Powers in logarithmic time

- Handling multiple cases and its effect on recursion diagram

- Recursive function with multiple recursive cases

- Direct translation of mathematical function to code

## 10. Sum Digits

- Extracting right most digit

- Chopping off right most digit

- Iterative solution

- Accumulator variable

- Time and space complexity

- Recursion diagram

- Reduce and combine

- Problem decomposition

- Recursive solution

- Time and space complexity

## 11. Guess a Number Game

- Game

- Computational complexity

- Derive the time complexity

## 12. Square Root

- Iterative solution

- Recursive solution using a wrapper function

- Comparison of iterative and recursive function

- Using bisection to improve performance

## 13. Reverse a String

- Recursive solution

- Multiple options in reduction step

- Combine step requires language builtin function

- Performance implications of concatenating strings

- Iteration solution using inplace modification of string

- Using two pointers

- Recursive solution with string inplace modification

- Using a wrapper function

## 14. Palindrome

- Problem size

- Multiple base cases

- Using two pointers

- Comparison with reverse a string problem

- Problem decomposition and its relationship to base cases

- Recursive solution

## 15. Print digits in reverse

- Prerequisites : Head and tail recursion, Add digits

- Size of the problem

- Base case

- Problem decomposition

- Recursion diagram: Reduction and combination

- Recursive solution

## 16. Find largest

- Problem decomposition

- Recursion diagram

- Combine step is a custom function

- Reducing by half

- Recursive function

- Two recursive calls

- Recursive solution

- Comparison of two versions

## 17. Contains Digit

- Problem Statement

- Program interface

- Assumption on input

- Linear recursive algorithm

- Recursion diagram

- Tail recursive algorithm

- Short circuit evaluation

- Relationship between base cases and recursive case

- One base case vs Two base cases

- Time complexity

- Similar problem

## 18. Equal Strings

- Interface (input and output)

- Base case

- Size of the problem

- Linear recursive algorithm

- Recursion diagram

- Problem decomposition

- Boolean function

- Recursive solution

- Tail recursive algorithm

- Short circuit evaluation

- Recursion diagram

- Comparison of linear and recursive solution

## 19. Factorial

- Problem definition

- Mathematical representation

- Translating mathematical function to recursive code

- Recurrence relation

- Deferred operation

- Subproblem with reduced argument

- Minimizing base cases

- Iterative solution

- Product accumulator

- Factorial call trace

- Factorial call and return table

- Pending multiplication direction

- Stack growth

- Time and space complexity

- Comparison of iterative and tail recursive solution

## 20 Fibonacci

- Problem Statement

- Recursive solution

- Two base cases

- Two recursive calls

- Recursive call tree

- Redundant calculations

- Binary Tree

- Level and number of nodes

- Total number of nodes

- Binary recursion runtime

- Improving performance by dynamic programming

- Time and space complexity

- Iterative solution

- Time and space complexity