Recursion

IB Standards

5.1.1 Identify a situation that requires the use of recursive thinking.
5.1.2 Identify recursive thinking in a specified problem solution.
5.1.3 Trace a recursive algorithm to express a solution to a problem.

Recursion is when a method calls itself until some termination condition is met. The basic idea behind recursion is to break down a big task into smaller subtasks. Each of those subtasks performs the same steps, and all return the same type. Recursion can let you iterate, or loop, without actually using a while/for/foreach loop. You might ask, “what’s the point of using recursion if I can just use a loop?”. This is a valid question and while it may seem unintuitive at first, the idea of recursion can help solve certain problems in computer science with elegant solutions. Some problems, like the one you’ll see in the problem set for this unit, require recursion to be solved effectively. In this particular case, a for loop would be overly cumbersome to use.

In the following video, we’re going to start with a quick overview of how recursion works at its simplest form. You will then be given a lab with 10 problems, each increasing in difficulty.