######### Recursion ######### You've seen functions that call other functions. If a function calls *itself*, we call that **recursion** Like with other functions, a call within a call establishes a *call stack* With recursion, if you are not careful, this stack can get *very* deep. Python has a maximum limit to how much it can recurse. This is intended to save your machine from running out of RAM. Recursion is especially useful for a particular set of problems. For example, take the case of the *factorial* function. In mathematics, the *factorial* of an integer is the result of multiplying that integer by every integer smaller than it down to 1. :: 5! == 5 * 4 * 3 * 2 * 1 We can use a recursive function nicely to model this mathematical function: :: 1! = 1 2! = 2 * 1 = 2 * 1! 3! = 3 * 2 * 1 = 3 * 2! So we have a pattern here -- each value can be defined in terms of the previous value. So generically:: 1! = 1 n! = n * (n-1)! How would we put that in code? Pretty straightforward translation: .. code-block:: python def factorial(n): return n * factorial(n-1) That was pretty easy -- what happens when we run it? .. code-block:: ipython In [2]: factorial(3) --------------------------------------------------------------------------- RecursionError Traceback (most recent call last) in () ----> 1 factorial(3) in factorial(n) 1 def factorial(n): ----> 2 return n * factorial(n-1) ... last 1 frames repeated, from the frame below ... in factorial(n) 1 def factorial(n): ----> 2 return n * factorial(n-1) RecursionError: maximum recursion depth exceeded OOPS! that didn't work -- why not? Let's add a print... .. code-block:: python def factorial(n): print("factorial called with", n) return n * factorial(n-1) And call it: .. code-block:: ipython In [5]: factorial(3) factorial called with 3 factorial called with 2 factorial called with 1 factorial called with 0 factorial called with -1 factorial called with -2 factorial called with -3 factorial called with -4 factorial called with -5 ... in factorial(n) 1 def factorial(n): 2 print("factorial called with", n) ----> 3 return n * factorial(n-1) RecursionError: maximum recursion depth exceeded while calling a Python object Now it's clear what's going on -- each time you call the function, it calls itself with a value one less -- but then it just keeps going into the deep negative numbers, and only stops because Python reaches its recursion limit. This makes clear a core requirement of recursive functions: **Recursive functions must have a termination criteria!** That is, there must be a case (or more than one) for which they return a direct value. What should that be for factorial? Well, it's part of the definition that 1! == 1 -- so let's put that in our function: .. code-block:: python def factorial(n): print("factorial called with", n) if n == 1: return 1 return n * factorial(n-1) and try that: .. code-block:: ipython In [7]: factorial(3) factorial called with 3 factorial called with 2 factorial called with 1 Out[7]: 6 Much better! Try it out now with various values, and maybe without the print: .. code-block:: ipython In [14]: factorial(1) Out[14]: 1 In [15]: factorial(2) Out[15]: 2 In [16]: factorial(3) Out[16]: 6 In [17]: factorial(4) Out[17]: 24 Looking good! Exercise for the reader: What happens if you pass in a negative number? Think about it first, before you try it. Hint -- it won't work! How would you change your code to make it more robust? Summary ------- * Whenever you have a function that can be defined in terms of itself, you have a use case for recursion. It can make for nice compact, clear code. * Python will create a new "stack frame" for each call to the function -- so each call is kept separate, with separate local variables. But: * Python has a limited recursion depth -- so it can't be used for "big" problems. * You do need to make sure the calls will terminate.