Back to course 'CS202: Discrete Structures'

Topic outline

  • Unit 6: Recursion

    Collapse all Expand all

    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

      • url icon
        Recursion Demystified URL
        Students must
        Mark as done

        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.

      • page icon
        Recursive Definitions Page
        Students must
        Mark as done

        Read this page to supplement to your understanding of recursion.

    • 6.2: Transitioning from Informal to Formal

      • page icon
        Collected Definitions of Recursion Page
        Students must
        Mark as done

        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.

      • page icon
        Explanation and Examples Page
        Students must
        Mark as done

        Read this page to get a sense of recursion from a mathematical basis.

      • page icon
        Illustrating Recursion Page
        Students must
        Mark as done

        This video explains recursion via illustration.

      • page icon
        Sequences and Recursion Page
        Students must
        Mark as done

        This video relates numeric sequences to recursion. There is also a discussion on notation.

    • 6.3: The Many Faces of Recursion

      • page icon
        The Many Faces of Recursion Page
        Students must
        Mark as done

        There are many ways to approach recursion. We take a look at those here.

      • book icon
        Try It Now Book
        Students must
        Mark as done

        Work these exercises to see how well you understand this material.

    • 6.4: Sequences

      • page icon
        Sequences Page
        Students must
        Mark as done

        In this subunit, we delve into progressions of numbers and their subsets. These progressions can be defined by recursive processes.

      • book icon
        Try It Now Book
        Students must
        Mark as done

        Work these exercises to see how well you understand this material.

    • 6.5: Recursion in the Real World

      • page icon
        Predicting Data Sample Values Page
        Students must
        Mark as done

        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

      • quiz icon
        Unit 6 Assessment Quiz
        Students must
        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.