## Wednesday, May 06, 2020

### Mastering Recursion Course Outline for Module 1

## 1. Head and Tail Recursion

- How to replace a loop with recursion?
- What is tail recursion?
- Differences between head and tail recursion?
- Tail recursion call tree

- 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

- 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