Skip to main content
Engineering LibreTexts

18.8: Recursion

  • Page ID
    16951
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    It is legal for one function to call another; it is also legal for a function to call itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical things a program can do. For example, look at the following function:

    def countdown(n):
        if n <= 0:
            print 'Blastoff!'
        else:
            print n
            countdown(n-1)
    

    If n is 0 or negative, it outputs the word, “Blastoff!” Otherwise, it outputs n and then calls a function named countdown—itself—passing n-1 as an argument.

    What happens if we call this function like this?

    >>> countdown(3)
    
    1. The execution of countdown begins with n=3, and since n is greater than 0, it outputs the value 3, and then calls itself...
    2. The execution of countdown begins with n=2, and since n is greater than 0, it outputs the value 2, and then calls itself...
    3. The execution of countdown begins with n=1, and since n is greater than 0, it outputs the value 1, and then calls itself...
    4. The execution of countdown begins with n=0, and since n is not greater than 0, it outputs the word, “Blastoff!” and then returns.
    5. The countdown that got n=1 returns.
    6. The countdown that got n=2 returns.
    7. The countdown that got n=3 returns.

    And then you’re back in __main__. So, the total output looks like this:

    3
    2
    1
    Blastoff!
    

    A function that calls itself is recursive; the process is called recursion.

    As another example, we can write a function that prints a string n times.

    def print_n(s, n):
        if n <= 0:
            return
        print s
        print_n(s, n-1)
    

    If n <= 0 the return statement exits the function. The flow of execution immediately returns to the caller, and the remaining lines of the function are not executed.

    The rest of the function is similar to countdown: if n is greater than 0, it displays s and then calls itself to display s n−1 additional times. So the number of lines of output is 1 + (n - 1), which adds up to n.

    For simple examples like this, it is probably easier to use a for loop. But we will see examples later that are hard to write with a for loop and easy to write with recursion, so it is good to start early.


    This page titled 18.8: Recursion is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press) .

    • Was this article helpful?