RecursionMemoization.md

Recursion & Memoization

Topics

• Revisit recursion with memoization
  • Fibonacci sequence
  • Change-making problem

Resources

• Play with VisuAlgo's interactive visualizations of recursion and memoization

• Read WikiBooks's Algorithms book chapter on memoization and dynamic programming

Challenges

• Implement the fibonacci function with memoization and dynamic programming using recursion starter code
  • Run python recursion.py <int> to test fibonacci function on a number argument
    • Example: python recursion.py 10 gives the result fibonacci(10) => 55
  • Run pytest recursion_test.py to run the recursion unit tests and fix any failures
  • Annotate functions with complexity analysis of running time and space (memory)
  • Benchmark performance of plain recursion versus memoized recursion
• Solve HackerRank's coin change problem and commit your solution code to your repository

Stretch Challenges

• Implement permutation and combination functions and optimize their performance using memoization
• Implement @memoized decorator function to easily memoize any recursive function