Recursion Preparation

Overview

Sometimes the most natural way to solve a problem is to first solve smaller versions of the same problem and then build on that solution. As strange as it might seem, methods are allowed to call themselves to accomplish just this sort of problem-solving approach. This is called recursion and it can be a bit tricky to wrap your head around at first. Depending on where you are coming from, you may have seen recursion quite a bit already or it may be totally new. That’s okay!

Basic Learning Objectives

Before class, you should be able to:

• Explain the high-level idea of recursion
• Explain how a method can call itself
• Explain what a base case is

Advanced Learning Objectives

After class, you should be able to:

• Explain the three laws of recursion
• Write a recursive function to solve a problem

Reading

You should read/watch the following (again, the code will be in Python but the ideas are the same):

• 4.2 What Is Recursion?
• 4.3 Calculating the Sum of a List of Numbers
• 4.4 The Three Laws of Recursion
• 4.5 Converting an Integer to a String in Any Base

Checks

Submit answers to the following on Moodle:

1. What are the three laws of recursion?

2. Implement the to_str recursive function from the reading section 4.5 in Kotlin: