Recursion and Tail Recursion

Today, we'll look at a fundamentally new way of developing algorithms and writing code using recursion.

Recursion occurs when a function that calls itself. It's a bit hard to describe why this is useful until you get a feel for it, but here's two high level points that eventually resonate:

Recursion offers a different approach to "repetition" in code without using loops. Perhaps surprisingly, this can be more intuitive for some problems.
Recursion allows us to model the self-similar structure that naturally exists in many interesting problems and data structures.

1: Introduction to Recursion

To start, let's take a look at the basic mechanism by which a function can call itself recursively and a quick example of where this is actually useful.

2: Solving Problems with Recursion

2.1 Not Started 2.2 Not Started

Here we'll try to build build an understanding of what sorts of problems are approachable using a recursive approach, how to extract a recurrence relation from a problem definition, and how to turn that into code.

Funny story… I recorded this video a couple years ago and in the background of that video you can clearly hear (e.g. @ 0:20) my son running around downstairs playing with this:

Oh well, at least it's somewhat related to the duck exercise.

2.1 Exercise: Counting Ducks, Part 1

Here's a copy of the duck exercise slide from the previous video:

We already know the value of $ducks(0)$ is $5$ , because that's the number of ducklings we start with (i.e. "after 0 months").

Write a recurrence relation for the number of ducks after $n$ months, $ducks(n) = ~ ???$ . Your recurrence should depend on the value(s) of the two previous months, e.g. $ducks(n-1)$ and $ducks(n-2)$ .

The walkthrough for this exercise is included with the walkthrough video for the second exercise below.

2.2 Exercise: Counting Ducks, Part 2

Translate your recurrence relation from Part 1 to code.

You're welcome to check your solution with this walkthrough video.

Note that this video covers BOTH part 1 and part 2 of the exercise. If you're here for part 1, you can pause partway through and come back.

3: Reversing an Array with Recursion

3.1 Not Started 3.2 Not Started

Let's consider an example of using recursion to processing a data structure - reversing an array.

We could do this iteratively with a loop, but what does it look like using recursion?

3.1 Exercise: Recursive Array Reverse, Part 1

Let's do a bit of brainstorming to come up with a recursive algorithm.

What base case could we use for reversing an array? What's the "simplest" possible array? What do you need to do to reverse it (if anything)?

What "subarray" would you reverse using the "recursive leap of faith"?

What do you need to do to finish the problem, assuming the subarray is reversed successfully?

You're welcome to check your solution with this walkthrough video.

3.2 Exercise: Recursive Array Reverse, Part 2

Translate your recurrence relation from Part 1 to code.

You're welcome to check your solution with this walkthrough video.

4: Tail Recursion

It turns out that recursion can be less memory-efficient than iteration in some cases due to a proliferation of stack frames. Let's take a look at a strategy called tail recursion that allows the compiler to perform optimizations to eliminate the inefficiency (in some cases).

In some cases, like the tail-recursive reverse() implementation, there's a natural approach to solve the problem using tail recursion. In other cases, like for factorial(), a more deliberate approach is necessary, including additional work to "pass a computed result forward" rather than computing a result as the call stack unwinds. Here's an example of an alternate approach that involves an extra accumlator parameter to implement a tail-recursive factorial() function.

You've reached the end of this lecture! Your work on any exercises will be saved if you re-open this page in the same web browser.

Participation Credit
Make sure to sign in to the page, complete each of the exercises, and double check the participation indicator at the top left of this page to ensure you've earned credit.