Unit 6: Recursion
Using recursion, we can arrive at a succession of elements (such as numbers or events) by operating on one or more of the elements that came earlier. We do this using a rule or formula with a finite number of steps. In computer programming, we implement recursion with procedures, subroutines, functions, or algorithms that run one or more times until a specified condition is met. At that point, the remaining code in each procedure is processed from the last procedure called to the first. From a practitioner's perspective, recursive procedures are simple to write, but they are extremely memory-intensive, and it can be difficult to predict how much memory will be required.
Recursion is common, so you will need to understand it at a fundamental level. A basic example of a recursive sequence is Dt = f(D[t-1]). The data at time t is a function of the data at the previous unit of time. In practice, this can be implemented as a recursive function or an explicit (that is, non-recursive) function. This unit will delve deeper into this topic.
Completing this unit should take you approximately 5 hours.
Upon successful completion of this unit, you will be able to:
- define linear recurrence and give examples;
- explain important recursive functions;
- produce recursively defined sequences; and
- write recursive relations that are defined in terms of themselves at increasingly-earlier moments in time.
6.1: Introduction
Recursion, something being defined in terms of a different version of itself, can be somewhat mystifying, so read this section for a gentle introduction before we move on to something more formal.
Read this page to supplement to your understanding of recursion.
6.2: Transitioning from Informal to Formal
Now, we will take a look at recursion from informal and formal perspectives that are related. Illustrations give us a practical sense of the matter. This approach prepares us for an increasingly-formal discussion. Read this page to see how recursion exists beyond mathematics and computer programming.
Read this page to get a sense of recursion from a mathematical basis.
This video explains recursion via illustration.
This video relates numeric sequences to recursion. There is also a discussion on notation.
6.3: The Many Faces of Recursion
There are many ways to approach recursion. We take a look at those here.
Work these exercises to see how well you understand this material.
6.4: Sequences
In this subunit, we delve into progressions of numbers and their subsets. These progressions can be defined by recursive processes.
Work these exercises to see how well you understand this material.
6.5: Recursion in the Real World
Read this example of a practical, complex, real-world problem that uses recursion in many ways. The underlying math is not testable, but try to get a sense of its subtle recursive nature.
Unit 6 Assessment
- Receive a grade
Take this assessment to see how well you understood this unit.
- This assessment does not count towards your grade. It is just for practice!
- You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.