10.13: Recursive Functions

Last updated
Save as PDF

Page ID: 14674

\( \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}}\)

Before you can learn how the floodFill() function works, you need to learn about recursion. Recursion is a simple concept: A recursive function is just a function that calls itself, like the one in the following program:

def passFortyTwoWhenYouCallThisFunction(param): print('Start of function.')
    if param != 42:
        print('You did not pass 42 when you called this function.')
        print('Fine. I will do it myself.')
        passFortyTwoWhenYouCallThisFunction(42) # this is the recursive call
    if param == 42:
        print('Thank you for passing 42 when you called this function.')
    print('End of function.')

passFortyTwoWhenYouCallThisFunction(41)

(In your own programs, don’t make functions have names as long as passFortyTwoWhenYouCallThisFunction(). I’m just being stupid and silly. Stupilly.)

When you run this program, the function gets defined when the def statement on line 1 executes. The next line of code that is executed is line 10, which calls passFortyTwoWhenYouCallThisFunction() and passes (gasp!) 41. As a result, the function calls itself on line 5 and passes 42. We call this call the recursive call.

This is what our program outputs:

Start of function.
You did not pass 42 when you called this function.
Fine. I will do it myself.
Start of function.
Thank you for passing 42 when you called this function.
End of function.
End of function.

Notice that the "Start of function." and "End of function." text appears twice. Let’s figure out what exactly happens and what order it happens in.

On line 10, the function is called and 41 is passed for the param parameter. Line 2 prints out "Start of function.". The condition on line 3 will be True (since 41 != 42) so Line 3 and 4 will print out their messages. Line 5 will then make a call, recursively, to the function and passes 42 for the param parameter. So execution starts on line B again and prints out "Start of function.". Line 3’s condition this time is False, so it skips to line 6 and finds that condition to be True. This causes line 7 to be called and displays "Thank you..." on the screen. Then the last line of the function, line 8, will execute to print out ―End of function.‖ and the function returns to the line that called it.

But remember, the line of code that called the function was line 5. And in this original call, param was set to 41. The code goes down to line G and checks the condition, which is False (since 41 == 42 is False) so it skips the print() call on line 7. Instead, it runs the print() call on line 8 which makes "End of function." display for a second time.

Since it has reached the end of the function, it returns to the line of code that called this function call, which was line 10. There are no more lines of code after line 10, so the program terminates.

Note that local variables are not just local to the function, but to a specific call of the function.