23. Recursion

Recursion is an algorithmic technique in which the solution defines itself in terms of the solution itself. A recursive solution continually solves smaller and smaller instances of itself until the solution reaches a base case.

Suppose you are waiting in line -

a very long line -

How can you figure out how many people are in front of you?

• You are not allowed to move

• You can only see the the person in front of you and behind you

• You can communicate with the person in front and behind you

Apply recursion!

number of people in front of you = # of people in front of the person in front of you + person in front of you

Solution:

• Tap the shoulder of the person in front of you and ask how many people are in front of him/her

• Wait for his/her response and then add 1

• If someone behinds you asks, tell them how many people are in front of you

Recursive algorithms have two main components:

• Base Case: Point where you stop applying the recursive and can answer the question directly

• Recursive Case: Set of instructions that will be executed repeatedly with smaller versions of the problem

Line count:

• Base case: no one is in front of me. Return 0

• Recursive case: return number of people in front of me + 1 (recursive call)

From a practical point of view with programming, a recursive function is any function that calls itself. Indirect recursion exists when a function invokes another function before the original function is called again without any returns. Recursive solutions will have cycles (loops) within the call graph.

For the line count, suppose we represent each individual as an entry in a list. The recursive solution would then look like -

def count_entries(my_list):
    if len(my_list) == 0:
        return 0
    else:
        return count_entries(my_list[0:-1]) + 1

print(count_entries(list(range(10))))

As you can see from the repetitive calls, recursion brings back the concept of repetition. Revisiting Python’s loop statements (while and for), both had methods to be able to stop the loop somehow. while has a condition check before we began each iteration of the loop. for has an implicit end to iteration once the sequence completes. Similarly, for recursive functions, we need to define a base case that allows the repetition to stop. This base case will be the simplest case of the problem itself:

• numerical: when computing a numeric answer, generally the base case will be for 0 or 1.

• structural: when processing data structures(lists, dictionaries, sets, etc.), the base case exists when that structure is empty or has no members of a particular type

The line counting used structural recursion as the recursive call processed smaller and smaller versions of the list. (And, yes, we could have simply just called len(my_list) to get the number of entries in the list.)

Computing factorials is the prototypical example to demonstrate numeric recursion. The factorial of a non-negative integer \(n\), denoted by \(n!\), is the product of all positive integers less than or equal to \(n\). The factorial of \(n\) also equals the product of \(n\) with the next smaller factorial:

\(n! = n\times (n-1)\times (n-2)\times (n-3)\times \cdots \times 3\times 2\times 1 = n\times (n-1)!\)

For example: \(5!=5\times 4\times 3\times 2\times 1=5\times 24=120\)

The value of \(0!\) is \(1\).

As you can see from the description, we have both the base case and the recursive case present in the definition.

• Base case: \(0! = 1\)

• Recursive case: \(n! = n \times (n-1)!\)

Here’s the Python implementation:

def factorial(n):
    """Return the factorial of n."""
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))

120

View execution on PythonTutor

As you can see from the factorial example, the def statement header looks just like other functions. We then have a conditional statement (if n == 0:) to check for the base case - these are evaluated without any further recursive call. Finally we have the recursive case (return n * factorial(n-1)) in which we solve for n in terms of a smaller version of the problem (factorial(n-1)).

23.1. Recursion Rules

Recursive algorithms must follow three rules:

• a recursive algorithm must call itself (recursive case)

• a recursive algorithm must have a base case

• a recursive algorithm must change its state and move towards the base case.

Look back over the line counting and factorial examples. How were these rules applied?

Before you run the following code block, what do you think occurs? Does say_hello() follow the recursion rules?

Go ahead and run it now. Seriously. Your computer won’t crash.

def say_hello():
    print("hello")
    say_hello()
    
say_hello()

Show code cell output Hide code cell output

hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[2], line 5
      2     print("hello")
      3     say_hello()
----> 5 say_hello()

Cell In[2], line 3, in say_hello()
      1 def say_hello():
      2     print("hello")
----> 3     say_hello()

Cell In[2], line 3, in say_hello()
      1 def say_hello():
      2     print("hello")
----> 3     say_hello()

    [... skipping similar frames: say_hello at line 3 (2972 times)]

Cell In[2], line 3, in say_hello()
      1 def say_hello():
      2     print("hello")
----> 3     say_hello()

Cell In[2], line 2, in say_hello()
      1 def say_hello():
----> 2     print("hello")
      3     say_hello()

File ~/Documents/GitHub/jupyternotebooks/venv/lib/python3.12/site-packages/ipykernel/iostream.py:664, in OutStream.write(self, string)
    655 def write(self, string: str) -> Optional[int]:  # type:ignore[override]
    656     """Write to current stream after encoding if necessary
    657 
    658     Returns
   (...)
    662 
    663     """
--> 664     parent = self.parent_header
    666     if not isinstance(string, str):
    667         msg = f"write() argument must be str, not {type(string)}"  # type:ignore[unreachable]

RecursionError: maximum recursion depth exceeded

You should have seen “hello” printed a large number of times followed by an error condition at the bottom of the output:

RecursionError: maximum recursion depth exceeded while calling a Python object

As a program makes function calls, Python must add a “stack frame” to keep track of the current function and its predecessors. This stack frame allows the interpreter to keep track of local namespaces for each function call. Before creating another “stack frame”, the interpreter checks how many instances exist – the number of function calls made without a corresponding return. If that number is beyond a certain threshold, then the Python interpreter assumes that a logic error has occurred, stops execution, and reports the recursion error. This “depth” is configurable. Other languages implement this check differently. For example, Java maintains a separate memory space and will have a memory error when the stack space is exhausted. The C and C++ standards do not specify a limit; the environment (operating system, other libraries, etc.) in which the program runs determines the available stack space.

say_hello() violated two of the recursive rules: no base case and no change in state to move towards the base case.

For printing a message, we track how many times the message has been printed (or, preferably, how many more times the message needs to be printed) and stop when that number is reached. The examples here will show both keeping track of a decreasing count as well as an increasing count. By convention(and “solving smaller instances of itself”), programmers write recursive functions with decreasing values. Of course, we could use a for loop with a range() to print the message.

def say_hello_increasing(count, max_count):
    if (count == max_count):
        return
    say_hello_increasing(count + 1, max_count)
    print('hello')
    
say_hello_increasing(0,5)

hello
hello
hello
hello
hello

def say_hello_decreasing(count):
    if (count == 0):
        return
    print("hello")
    say_hello_decreasing(count - 1)
    
say_hello_decreasing(5)

hello
hello
hello
hello
hello

Notice that the latter function is also less complex in that we did not need to track the maximum number of messages to print. Our initial call implicitly defines this value.

View say hello decreasing on pythontutor.com

23.2. Defensive Programming

Defensive programming is the practice of writing code such that the code continues to function correctly even if used in a manner that was not originally intended or imagined. Defensive programming strives to reduce the number of potential problems by using slightly different logic that still meets the original intent.

As mentioned, Python is a dynamically, strongly typed language. By dynamic, the types are determined at runtime. By strongly typed, the interpreter enforces which operations variables and expressions may participate based on type. In contrast, C, C++, and Java are statically typed. C is considered weakly typed as type checking is not strongly enforced - an assumption exists that programmers know what they are doing. C++ has much stronger type checking during the compilation process and is considered strongly typed. Java has both static checks during compilation as well as runtime checks. [Ada](https://en.wikipedia.org/wiki/Ada_(programming_language) is most likely the strongest-typed language.

As one of the effects of being dynamically typed, it is possible to use different types than the programmer originally intended as long as the operations or methods called on that type are supported.

What happens if we make this function call - say_hello_decreasing(5.5)? How many messages will appear?

say_hello_decreasing(5.5)

Show code cell output Hide code cell output

hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello
hello

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[5], line 1
----> 1 say_hello_decreasing(5.5)

Cell In[4], line 5, in say_hello_decreasing(count)
      3     return
      4 print("hello")
----> 5 say_hello_decreasing(count - 1)

Cell In[4], line 5, in say_hello_decreasing(count)
      3     return
      4 print("hello")
----> 5 say_hello_decreasing(count - 1)

    [... skipping similar frames: say_hello_decreasing at line 5 (2972 times)]

Cell In[4], line 5, in say_hello_decreasing(count)
      3     return
      4 print("hello")
----> 5 say_hello_decreasing(count - 1)

Cell In[4], line 4, in say_hello_decreasing(count)
      2 if (count == 0):
      3     return
----> 4 print("hello")
      5 say_hello_decreasing(count - 1)

File ~/Documents/GitHub/jupyternotebooks/venv/lib/python3.12/site-packages/ipykernel/iostream.py:664, in OutStream.write(self, string)
    655 def write(self, string: str) -> Optional[int]:  # type:ignore[override]
    656     """Write to current stream after encoding if necessary
    657 
    658     Returns
   (...)
    662 
    663     """
--> 664     parent = self.parent_header
    666     if not isinstance(string, str):
    667         msg = f"write() argument must be str, not {type(string)}"  # type:ignore[unreachable]

RecursionError: maximum recursion depth exceeded

oops…

Since say_hello_decreasing() had an equality check against zero, that condition never evaluated to True and the base condition was “blown through”.

We can modify the condition to be more “forgiving” and, hence, prevent potential mishaps

def say_hello_defensive(count):
    if (count <= 0):
        return
    print("hello")
    say_hello_defensive(count - 1)
    
say_hello_defensive(5)

hello
hello
hello
hello
hello

A slightly different but equivalent version. Two differences:

1. The function performs some activity first.

2. Function checks for the base case before making the recursive call.

def say_hello_defensive_alternate(count):
    print("hello")
    if (count > 0):
        say_hello_defensive_alternate(count - 1)
    
say_hello_defensive_alternate(5)

hello
hello
hello
hello
hello
hello

Which approach is better? As with just about any answer with consulting, it depends. The second function will always print at least one message. What is the desired behavior?

23.3. Example: Summing a List

While recursion is not an optimal way to sum a list (a for loop is more appropriate, using the built-in function sum is the best approach), programmers can use recursion for this task.

So to approach a recursive solution, revisit the Seven Steps and work through some sample cases by hand first.

The sum of an empty list is 0. The sum of a list with just one element is that element itself. A negative length for a list is illogical.

So how about a list of four numbers: \([a, b, c, d]\)?

\(sum = a + b + c + d \)

Applying associativity, what are the different possibilities?

\(sum = a + b + (c + d) \)
\(sum = a + (b + c + d) \)
\(sum = (a + b) + (c + d) \)
\(sum = (a + b + c) + d \)
\(sum = (a + b ) + c + d \)

The second and fourth possibilities might be a good pattern for us. Take the second - so the sum equals the first number \(a\) plus the rest of the list \([b,c,d]\) We have just created a smaller instance. Now, the sum of \([b,c,d] = b + c + d = b + (c + d)\)

Now, write pseudocode for this:

    input: list of numbers
    output: sum
    algorithm:
      function sum_list(list)
         if length(list) = 0, return 0
         else if length(list) = 1, return the first element (list[0])
         else return list[0] + sum of the rest of the list

Anything to generalize? The condition for the list with only one element could be expressed as the first number plus an empty list. That simplifies our logic at the small cost of an extra function call.

Step through a couple of sample lists manually to see how our approach works: [] [5] [1,2] [1,2,3]

Time to translate the pseudocode to Python. Remember how to slice lists?

def sum_list(list_to_sum):
    if len(list_to_sum) == 0:
        return 0
    return list_to_sum[0] + sum_list(list_to_sum[1:])

print("[]:", sum_list([]))
print("[5]:", sum_list([5]))
print("[1,2,3]:", sum_list([1,2,3]))
print("[1,2,3,4,5,6,7,8,9,10]:", sum_list([1,2,3,4,5,6,7,8,9,10]))

[]: 0
[5]: 5
[1,2,3]: 6
[1,2,3,4,5,6,7,8,9,10]: 55

View on PythonTutor

Note: Intermediary variables were added to the code on PythonTutor to demonstrate the program’s state as shown below.

def sum_list(list_to_sum):
    if len(list_to_sum) == 0:
        return 0
    
    current_value = list_to_sum[0]
    recursive_value = sum_list(list_to_sum[1:])
    result = current_value + recursive_value
    return result

Adding intermediary variables like this may help debugging. By separating and making explicit the different steps, it becomes easier to analyze. Using a debugger, programmers can step through each code line and follow the variables’ changes. The variable names provide additional context as well.

23.4. Case Study: Recursive Directory Listings

In a previous notebook, we learned the basic operations to perform directory and file operations.

One common task with filesystems is to list all of the files within a particularly directory, including any subdirectories, as well as any subdirectories those may have, then subdirectories within those subdirectories, and then …

As you can read, traversing a directory and all of the children can become complex - a priori, we do not know the depth of the directory structure. Nor do we want to code for a specific structure depth; we are after generalized solutions.

Solving this for just the initial directory is simply just listing the contents of that directory. However, as we iterate through that list, we need to ask ourselves what to do for each file based on its type:

• file: just print the name

• directory: print the name, and then list the contents of that directory.

Ah, we have just defined the solution in terms of itself. Now, what is the base case? Is the directory empty? Sure, but no guarantee that an empty directory exists. So when do we stop making function calls? When a directory doesnʼt contain any more subdirectories. In this situation, an explicit base condition does not exist; instead, the base condition occurs implicitly based on the directory’s contents.

import os

def walk_directory(directory_name):
    files = os.listdir(directory_name)
    for file in files:
        print(file)
        test_filename = os.path.join(directory_name,file)
        if (os.path.isdir(test_filename)):
            walk_directory(test_filename)
        
walk_directory(".")

02-ProblemSolvingByProgramming.ipynb
09.b-FormattingStrings-fStrings.ipynb
22-Validation,ExceptionsAndErrorHandling.ipynb
13-Iteration.ipynb
26-ClassesAndObjects-Inheritance.ipynb
25-ClassesAndObjects.ipynb
28-DateTime.ipynb
answers
other-Tuples-Answers.ipynb
05-Control-Answers.ipynb
19-Recursion-Answers.ipynb
rq-26-answers.md
rq-11-answers.md
10-Lists-Answers.ipynb
rq-05-answers.md
blastText.txt
rq-19-answers.md
rq-08-answers.md
rq-14-answers.md
rq-23-answers.md
rq-13-answers.md
rq-24-answers.md
other
34-Comprehensions.ipynb
36-RegularExpressions-Answers.ipynb
15.2-FileOperations-Answers.ipynb
rq-02-answers.md
03-Answers
rq-07-answers.md
12-RandomNumbers-Answers.ipynb
rq-21-answers.md
rq-16-answers.md
06-Functions-Answers.ipynb
rq-04-answers.md
rq-18-answers.md
rq-09-answers.md
rq-15-answers.md
04-BasicInputAndOutput-Answers.ipynb
09-FormattingStrings-Answers.ipynb
rq-10-answers.md
rq-01-answers.md
12-Iteration-Answers.ipynb
.ipynb_checkpoints
36-RegularExpressions-Answers-checkpoint.ipynb
04-Answers-checkpoint.ipynb
08-Answers-checkpoint.ipynb
05-Answers-checkpoint.ipynb
15 - Files-checkpoint.ipynb
07-Answers-checkpoint.ipynb
19-Recursion-Answers-checkpoint.ipynb
11-Answers-checkpoint.ipynb
10-Answers-checkpoint.ipynb
06-Answers-checkpoint.ipynb
16-Files-Answers.ipynb
rq-06-answers.md
14-Dictionaries-Answers.ipynb
rq-20-answers.md
rq-17-answers.md
08-Strings-Answers.ipynb
rq-12-answers.md
rq-25-answers.md
rq-03-answers.md
images
fencepost.png
median_original.png
ifElseStatement.png
TrafficLights.png
faultProgression.png
sw_lifecycle.png
calculate_price.png
ClassAttributesMethods.png
calculate_price_original.png
calculate_price.psd
automata
abc.png
a.png
abstar.png
aplus.png
defectCost.jpeg
string-slicing.png
recursion
long_line.png
line.png
ifElifStatement.png
pacman256.png
ayn_random_XKCD.png
array.png
debugging
dataflow.png
median.png
mothMarkII_1947.jpeg
set_operations.png
sevensteps.png
playgolf.png
variable_reference.png
DiamondProblem.png
suduko.png
pm_swing.jpeg
prob_algo_prog.png
whileStatment.png
ifStatement.png
namespace.png
EmployeeClassHierarchy.png
lego_bricks.jpg
calculate_price_label.png
.ipynb_checkpoints
runtime_cases.png
wordcount.png
relevantXKCD.png
27-Comprehensions.ipynb
14-Dictionaries.ipynb
09-FormattingStrings.ipynb
resources
therac25.pdf
python_overloading.pdf
17-Files.ipynb
19-Errors.ipynb
21-Modules.ipynb
07-Functions.ipynb
10-Lists.ipynb
03-Types,Values,Variables,Names.ipynb
08.a-Strings-OtherFunctions.ipynb
newDir
newSubDir
dickens.txt
README.md
04-Boolean,Numbers,Operations.ipynb
12-RandomNumbers.ipynb
06-Control.ipynb
23-Testing.ipynb
18-FileOperations.ipynb
16-Miscellaneous.ipynb
01-Introduction.ipynb
11-Tuples.ipynb
29-RegularExpressions.ipynb
test.txt
.ipynb_checkpoints
19-Recursion-checkpoint.ipynb
20-Modules-checkpoint.ipynb
26-DateTime-checkpoint.ipynb
02-ProblemSolvingByProgramming-checkpoint.ipynb
05-BasicInputAndOutput-checkpoint.ipynb
10-Lists-checkpoint.ipynb
14-Dictionaries-checkpoint.ipynb
09.b-FormattingStrings-fStrings-checkpoint.ipynb
01-Introduction-checkpoint.ipynb
15-Sets-checkpoint.ipynb
11-Tuples-checkpoint.ipynb
18-Recursion-checkpoint.ipynb
18-FileOperations-checkpoint.ipynb
22-Testing-checkpoint.ipynb
09-FormattingStrings-checkpoint.ipynb
16-Miscellaneous-checkpoint.ipynb
19-Errors-checkpoint.ipynb
07-Functions-checkpoint.ipynb
06-Control-checkpoint.ipynb
21-Validation,ExceptionsAndErrorHandling-checkpoint.ipynb
24-ClassesAndObjects-checkpoint.ipynb
03-Types,Values,Variables,Names-checkpoint.ipynb
26-Comprehensions-checkpoint.ipynb
25-ClassesAndObjects-Inheritance-checkpoint.ipynb
08-Strings-checkpoint.ipynb
Untitled-checkpoint.ipynb
27-RegularExpressions-checkpoint.ipynb
28-RegularExpressions-checkpoint.ipynb
12-RandomNumbers-checkpoint.ipynb
23-Debugging-checkpoint.ipynb
21-Testing-checkpoint.ipynb
04-Boolean,Numbers,Operations-checkpoint.ipynb
17-Files-checkpoint.ipynb
27-DateTime-checkpoint.ipynb
13-Iteration-checkpoint.ipynb
15-Sets.ipynb
20-Recursion.ipynb
data
djia_returns_1886_2022.csv
state_populations.txt
GME.csv
grades.txt
TSLA.csv
SPY.csv
PakistanSuicideAttacks.csv
AAPL.csv
05-BasicInputAndOutput.ipynb
09.a-FormattingStrings-OldStyle.ipynb
08-Strings.ipynb
24-Debugging.ipynb

23.5. Recursion Notes

23.5.1. Head and Tail Recursion

Two types of recursive functions exist - head recursion and tail recursion.

For head recursion, the recursive call comes first, then any other processing in the function. say_hello_increasing() is an example of head recursion. Note that we had the base condition check executed first. If the recursive call had occurred first, then a stack overflow error would have happened as the condition for calling the function never changed.

In tail recursion, the function’s processing comes first, followed by the recursive call. walk_directory() is an example of tail recursion. Tail recursion enables an optimization technique known as tail call optimization (TCO). In a tail-recursive function, the final action of the function is a call to itself, potentially allowing the compiler or interpreter to optimize the recursion by reusing the current function’s stack frame instead of creating a new one. This optimization can transform the recursive process into an iterative one, effectively making the recursive function as efficient as a loop. From a memory standpoint, each recursive call would add a new frame to the call stack, potentially leading to a stack overflow if the recursion depth is too large. Tail recursion helps to mitigate this risk by ensuring that no additional stack space is needed for each recursive call when TCO is applied, thus allowing recursion to be used even in cases with deep recursion levels without running out of stack space.

Python does not implement TCO while many C++ compilers do implement this optimization. This chapter from The Recursive Book of Recursion discuss reasoning behind the choice not to implement as well as an argument as to why not to worry about the concept. Worry about writing correct code that is understandable.

23.5.2. Wrapper Functions

Often, we may want to initiate a recursive algorithm but initially perform one or more of the following items as part of that process:

• validate parameters

• initialize any parameters or auxiliary variables. Often, we may want to keep track of the stack depth ourselves

• handle any exceptions and errors. (We cover these soon.)

For these situations, use a wrapper function to perform these tasks. A wrapper function exists where the primary purpose is to call another routine. In this situation, we write and then utilize a wrapper function to validate the parameters and then to correctly call the recursive function. One of the other features of Python is the ability to nest function(s) within a function. This nesting prevents code outside of our function from calling the nested functions. So external code in this situation cannot directly call the recursive function.

import sys

def say_hello(num_times):
    def say_hello_increasing(count, max_count):
        if (count == max_count):
            return
        say_hello_increasing(count + 1, max_count)
        print('hello')
    
    if (num_times < 0):
        print("num_times cannot be negative")
        return
    if (num_times >= sys.getrecursionlimit()): 
        print("num_times greater than or equal to the recursion limit")
        return
    say_hello_increasing(0, num_times)
    
say_hello(-1)
say_hello(5)
say_hello(sys.getrecursionlimit())

num_times cannot be negative
hello
hello
hello
hello
hello
num_times greater than or equal to the recursion limit

What is the actual value for sys.getrecursionlimit() in your environment? What is the largest value you can successfully pass to say_hello without causing an error? Why does this discrepancy exist?

Notice that the inner function say_hello_increasing() needed to be defined first. Try re-writing the code such that the function definition occurs last. What error occurred?

# reorder say_hello such that say_hello_increasing is the first line in the function
def say_hello(num_times):
    def say_hello_increasing(count, max_count):
        if (count == max_count):
            return
        say_hello_increasing(count + 1, max_count)
        print('hello')
        
    say_hello_increasing(0, num_times)
    


say_hello(5)

hello
hello
hello
hello
hello

23.6. Verifying Correctness

To verify a recursive algorithm is correct, we need to show that both a base case and a recursive case exist within the algorithm.

We can also apply mathematical induction to prove a numerical recursive algorithm works correctly.

In mathematical induction, we show:

1. The base / initial case holds. Often this is fairly trivial. \(0! = 1\)

2. Inductive step. For every \(n\), we demonstrate that the algorithm also holds for \(n+1\). We assume \(n\) is true. For our use, we can equivalently assume \(n-1\) is true, and then demonstrate that \(n\) holds.

Going back to the recursive algorithm for factorial:

def factorial(n):
    """Return the factorial of n."""
    if n == 0:
        return 1
   else:
        return n * factorial(n-1)

Proof:

• Basic step (n=0): We can see that factorial(0) \(= 1\)

• Inductive step: Assume the algorithm correctly computes (n-1)! for factorial(n-1). Then for factorial(n), the recursive case computes \(n * (n-1)! = n!\), which is the correct value for factorial(n).

23.7. Common Recursive Issues

Several issues can arise when using recursion:

1. No update exists to the data prior to the recursive call. In this situation, we have not reduced the problem into a smaller subprogram. This leads to a RecursionError as the function will just be called from itself without any change.

2. The base case is incorrect. Earlier in this notebook, we showed the issue where we missed the base case due to an overly strict conditional check. Other instances will occur when not all bases are appropriate defined. As you will be asked in one of the exercises to compute Fibonacci numbers, you will see that two base cases exist.

3. Data within the function references a mutable data structure that is changed during the function. As many recursive calls exist, tracking changes to the data can be problematic.

23.8. Reentrancy

The last issue brings up a concept within computing termed “reentrancy”. Functions are considered reentrant if multiple invocations can be safely executed concurrently. Such concurrency exists on multi-processor system or when a procedure is temporarily interrupted (paused) to allow another thread/process to execute the function as well. This situation frequently occurs within web applications. Typically, a function exists that serves as a route (an endpoint) for a particular URL. As many clients can request that URL simultaneously, the code that handles the request must allow for reentrancy. While the Wikipedia page provides several rules functions should follow to be reentrant, the follow conditions suffice:

• State needs to be maintained within parameters and local variables

• Access to static variables (discussed in classes) and global variables must be read only. This also requires that other code does not modify those variables. If those variables can be modified, the access to the variables must be synchronized. This is an advanced topic covered elsewhere.

• The function can not share references to mutable objects (such as lists) - either within calls to itself or elsewhere within the program. Mutability means that we can not be sure that the object has been modified.

You should strive to make your code reentrant whenever possible. Such code tends to avoid side-effects and is general easier to debug. When multiple parts of a program or different processes can change problems it becomes difficult both to reproduce an issue as well as to track the issue’s root cause.

Credit: https://thomaspark.co/2017/01/relevant-xkcd/

23.9. Suggested LLM Prompts

• Explain the concept of recursion and its importance in programming. Describe the key components of a recursive function, such as the base case and the recursive case. Provide a simple example of a recursive function in Python, like calculating the factorial of a number.

• Compare and contrast recursion with iterative approaches. Discuss the advantages and disadvantages of each approach, and provide examples of problems that are better suited for recursion or iteration. Explain when recursion might be a more elegant or efficient solution.

• Explain how to visualize the execution of a recursive function using a call stack or a recursion tree. Provide a step-by-step example of how a recursive function is executed, showing the state of the call stack or recursion tree at each step.

• Explain the concept of tail recursion and its significance in Python. Discuss how tail recursion can be optimized by the compiler or interpreter and how it can improve the efficiency of recursive functions. Provide examples of tail-recursive functions in Python.

• Introduce common recursive algorithms, such as the merge sort algorithm, quicksort, and the Fibonacci sequence calculation. Explain the recursive approach used in these algorithms and provide Python implementations.

• Discuss the concept of memoization and how it can be used to optimize recursive functions by caching previously computed results. Provide examples of recursive functions that can benefit from memoization and show how to implement memoization in Python.

• Compare and contrast structural versus numerical recursion.

• Discuss strategies for debugging and testing recursive functions, which can be challenging due to the nested function calls and changing state. Provide tips and best practices for writing testable and maintainable recursive code in Python. (Note: while this guide has to spend a detailed overview of debugging and testing, we urge you to return to this prompt afte you have read those pages.)

23.10. Review Questions

1. What is recursion, and how does it differ from iteration?

2. What are the two essential components of a recursive function?

3. Explain the concept of a base case in a recursive function.

4. What is the role of the recursive case in a recursive function?

5. How would you go about showing that your recursive algorithm always terminates?

6. Explain indirect recursion.

7. What is the purpose of a wrapper function?

8. Explain the difference between head and tail recursion.

9. Explain the difference between numerical and structural recursion. Provide an example of each.

10. Explain three possible risks or disadvantages of recursion.

answers

23.11. Exercises

1. Write a recursive function to compute the nth Fibonacci number. This function should have the signature fibonacci(n) Computing Fiboannic numbers is the other standard example often used for recursion. Again, we leave it as an exercise for the reader.

2. Sum a list. However, an element may be a number, a list, or a string. Ignore strings.To test if a variable is a string, use type(variable_name) is str; to test if a variable is a list, use type(variable_name) is list.

3. Implement a modified version of the Linux command-line program tree as a recursive function. Below is the output. In this example, we called the function with the current directory as the argument. List the files and directories in alphabetical order. The number in parenthesis is the size of the file in bytes. At the bottom of the output, display the number of directories and files underneath the initial directory. Do not include the initial directory in the count. The final number is the total number of bytes allocated to the entire structure, including the initial directory. The starting point for the code should be the function tree(directory_name). You can assume there will always be multiple files and directories. i.e., you do not have to special case the plurals for this problem. Show all files - including hidden files (those that start with a period). Implementation note: to be able to reference a variable defined by an outer function within a nested function, use the nonlocal keyword. This functions similarly to the global keyword used when discussing namespaces.

   .
   ├── 00-Preliminaries.ipynb (456,333)
   ├── 01-Introduction.ipynb (799,312)
   ├── answers
   │   ├── 02-Answers (23,333)
   │   ├── 03-Answers (76,566)
   ├── data
   │   ├── PakistanSuicideAttacks.csv (264,320)
   │   ├── djia_returns_1886_2022.csv (56,203)
   │   └── state_populations.txt (25,850)
   ├── images
   │   ├── ifElifStatement.png (45,045) 
   │   ├── ifElseStatement.png (47,334)
   3 directories, 9 files
   2,345,333 bytes