Module #12
In this module you will learn about functions that are defined by calling itself -- recursive functions.
Recursion
A recursive function is a function that's defined in terms of itself.
That is:
- within the definition of a function...
- that same function is called!
- which can be used to implement repetition without loops!
- note that the recursive function can't complete until the call to itself completes (which may in turn, call itself again)...
Here's an example of a recursive function that prints and increments a number... and calls itself again, resulting in never-ending count:
def print_and_inc(n=0):
print(n)
print_and_inc(n + 1)
print_and_inc()Note that when this is run, the count seemingly goes on forever, until it stops due to a runtime exception:
- because the initial call to print_and_inc is waiting for the inner call to return... which in turn is also waiting for an inner function call to return (and so on)... there are multiple functions that have not finished executing
- consequently, Python stops the program from running due to the number of nested functions waiting to finish!
For a more practical recursive function, we eventually want to stop calling the function so that we don't get this error. Maybe we can have a condition that ends the function rather than calls the function again! This condition, the condition where the recursive function is not called again, is called the base case. Let's fix our previous program so that the count is finite.
def print_and_inc(n, m):
print(n)
if n == m:
return
else:
print_and_inc(n + 1, m)
print_and_inc(0, 10)Sample Program: Recursively build a dictionary from two element tuples, using the first element as a key, and the second element as the value.
Quiz
Now that you've completed this module, please visit our NYU Classes site and take the corresponding quiz for this module. These quizzes are worth 5% of your total grade and are a great way to test your Python skills! You may also use the following scratch space to test out any code you want.