22.1.2. Recursion and Base Cases

Try these first

1. 1.

   What is recursion?

   Hint

   Think about solving a problem in smaller steps.

2. 2.

   Define a base case in recursion.

   Hint

   Consider the smallest instance of a problem.

3. 3.

   What does recursion allow us to do in algorithms?

   • Solve all problems in one step
   • Break problems down into smaller steps
   • Ignore previous calculations

   Hint

   Think about how we solve difficult problems more easily.

4. 4.

   True or False: The base case is necessary to prevent infinite recursion.

   • True
   • False

   Hint

   What happens if there is no end point?

5. 5.

   Design a unique Huffman coding tree for the letters A, B, C, D with frequencies 10, 20, 30, 40, and explain the optimality of each step.

   Hint

   Consider which two letters you would merge first.

6. 6.

   Discuss how you would adjust your Huffman tree if the frequency of letter Z increases significantly. What does this imply for recursion?

   Hint

   Look at how new frequencies shape the overall structure.