2.1.5. Challenges with Recursion

Try these first

1. 1.

   Define recursion in your own words.

   Hint

   Think of how a task can be broken down into smaller, similar tasks.

2. 2.

   What is a base case in recursion?

   Hint

   Consider the simplest form of a problem to illustrate what the base case is.

3. 3.

   What does recursion rely on to solve problems?

   • Iterative methods
   • Function calls
   • User input

   Hint

   Think of how a problem can be simplified into smaller versions.

4. 4.

   True or False: In dynamic programming, paths through holes are calculated as non-existent.

   • True
   • False

   Hint

   Consider how you would navigate around obstacles.

5. 5.

   Calculate the number of unique paths in a grid with dimensions 5x5 but with holes at (2,2) and (3,3).

   Hint

   Consider using dynamic programming to fill out each cell based on its neighbors.

6. 6.

   Demonstrate how using recursion for grid paths can lead to a time complexity issue. Define an example and show how memoization would resolve it.

   Hint

   Think about overlapping subproblems and how caching can optimize the process.