- 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
