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.
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.
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.
This video relates numeric sequences to recursion. There is also a discussion on notation.
There are many ways to approach recursion. We take a look at those here.
In this subunit, we delve into progressions of numbers and their subsets. These progressions can be defined by recursive processes.
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.
Take this assessment to see how well you understood this unit.