Recursive Functions To Piss Off Your CS Professor
Posted by Al Sweigart in misc
Here are some recursive functions that are technically correct and technically recursive.
The programs here are available in a git repository.
(Explaining the joke kills the humor, but explanations have been given at the bottom if you aren't familiar with recursive programming. Input validation in these functions has been skipped for brevity.)
Factorial
def fact(num):
# Base cases:
if num == 0: return 1
elif num == 1: return 1
elif num == 2: return 2
elif num == 3: return 6
elif num == 4: return 24
elif num == 5: return 120
elif num == 6: return 720
elif num == 7: return 5040
elif num == 8: return 40320
elif num == 9: return 362880
elif num == 10: return 3628800
# Skip the base case for 11.
elif num == 12: return 479001600
elif num == 13: return 6227020800
elif num == 14: return 87178291200
elif num == 15: return 1307674368000
elif num == 16: return 20922789888000
elif num == 17: return 355687428096000
elif num == 18: return 6402373705728000
elif num == 19: return 121645100408832000
elif num == 20: return 2432902008176640000
# Recursive case:
else: return num * fact(num - 1)
Fibonacci
fib_cache = [None, 0, 1] # Memoization cache with base cases
def fibonacci(nth):
# Check if nth fib number is in the cache:
if len(fib_cache) <= nth:
return fib_cache[nth]
else:
# If not, expand the cache:
b = fib_cache[len(fib_cache) - 1]
a = fib_cache[len(fib_cache) - 2]
while len(fib_cache) < nth:
b, a = a + b, b
fib_cache.append(b)
# Recursive case:
return fibonacci(nth - 1) + fibonacci(nth - 2)
Even Odd Detection
def is_odd(num, originally_positive=None):
# Base case:
if num == 0:
return False
# Determine argument for originally_positive:
if originally_positive == None:
if num > 0:
return not is_odd(num - 1, True)
else:
return not is_odd(num + 1, False)
# Recursive cases:
if originally_positive:
return not is_odd(num - 1, True)
else:
return not is_odd(num + 1, False)
Depth First Search
import random
data = {'key': 'a', 'value': 42, 'branches': [
{'key': 'c', 'value': 13, 'branches': []},
{'key': 'z', 'value': 21, 'branches': [
{'key': 'x', 'value': -5, 'branches': []}
]}
]}
def dfs(needle, haystack):
if haystack['key'] == needle:
# Key found base case:
return haystack['value']
for branch in haystack['branches']:
# Recursively check each of the branches:
try:
return dfs(needle, branch)
except KeyError:
# Check again sometimes, just to make sure:
if random.randint(0, 1) == 1:
try:
return dfs(needle, branch)
except KeyError:
pass
# Key not found base case:
raise KeyError
Joke Explanations
Before you tell me some nitpick about why this code is wrong or a suggestion about how I should have written the code some other way, remember the MST3K mantra: "It's just a show, I should really just relax."
And then you should keep the nitpick or suggestion to yourself.
Factorial Explanation
The factorial of an integer is the product of all integers from 1 up the integer. For example, the factorial of 5 (written as 5! in mathematics) is 5 x 4 x 3 x 2 x 1 or 120.
Recursive functions need to have at least one base case (or else it will eventually cause a stack overflow) and at least one recursive case (or else it isn't recursive). This can be done recursive because 5! is the same thing as 5 x 4!, and 4! is the same thing as 4 x 3!, and so on.
Recursive factorial only needs one base case: 0! is 1. However, the gag here is that I supply several base cases, effectively getting rid of the need for any recursion for the integers 0 through 20. The function still uses recursion for integers larger than 21, but you could theoretically have millions or billions of base cases and still technically claim this is a recursive function. You are effectively hard-coding the recursion away.
(This sort of pre-calculated caching is called memoization.)
Bonus joke: I skipped the base case for 11 for absolutely no reason. The function still works for finding 11!.
Fibonacci Explanation
The Fibonacci sequence starts with the numbers 0 and 1. Each subsequent number in the sequence is the sum of the previous two numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on forever. It's a pattern that comes up in nature.
The base cases are for the 1st and 2nd Fibonacci numbers: 0 and 1, respectively. You can determine the Nth Fibonacci number by adding the Nth - 1 and Nth - 2 Fibonacci numbers. This lends itself well to recursion, however it results in a staggering amount of recalculation: Finding fibonacci(5) means finding fibonacci(4) and fibonacci(3), but finding fibonacci(4) involves finding fibonacci(3) and fibonacci(2). The fibonacci(3) call is made multiple times, even though the 3rd Fibonacci number doesn't change and doesn't need to be recalculated.
This issue of overlapping subproblems is solved by memoization, or the caching of results already calculated.
The gag here is that when the given Fibonacci number hasn't been calculated, the cache is populated by iteratively calculating the Fibonacci number. The two recursive calls are then made (making this a recursive function), even though the answer already exists in the cache. The recursion here is compeltely pointless.
Even Odd Detection Explanation
Determining if an integer is even or odd is straightforward in programming: mod the number by two and if the result is 0 it is even and if the result is 1 it is odd. The Python code is:
def is_odd(num):
return num % 2
def is_even(num):
return not (num % 2)
But this can also be done recursively. Is the integer 42 even or odd? Well, the answer is the opposite of whether 41 is even or odd. And 41's oddness is the opposite of 40's oddness, and so on. The base case is that 0 is an even number.
The gag here is that the mod approach works in one step for any number, the recursive approach gets slower and slower the larger the number is: finding out if 1,000,000,000 requires a billion function calls to determine if it is odd or not.
Let's make this even worse by unnecessarily splitting the recursive case into two recursive cases: whether the number argument was originally positive or negative by storing this information in a parameter. This is similar to the way certain recursive functions use an accumulator parameter for their operation. (My opinion is that any recursive function has an accumulator, it can always be done easier without using recursion.)
Depth First Search Explanation
Depth first search is an algorithm for finding data in a tree data structure. Recursion is actually a suitable solution for this, as it involves 1) tree-like data structures and 2) backtracking. If your problem doesn't have both of these features, then recursion is an messy, overengineered approach.
We have a tree data structure where each node has a key-value pair and branches to other nodes. The root node of the tree is passed to the dfs() function along with the key to search for. If the root node's key matches the key we are searching for, it returns the value in that key-value pair. This is the first of two base cases.
Otherwise, dfs() is called on each of the branches of that node. This is the recursive case. In this way, the entire tree is searched. If the recursion stops at nodes that do not have any branches. If we return from all the recursive calls without finding the key, the KeyError exception is raised to indicate that the key doesn't exist in the tree. This is the second base case.
The gag here is that, randomly, the function will re-check the branches of the node. The function is still technically recursive, though it makes far more recursive function calls than needed.
A similar joke is in my Poisoned Merge Sort implementation, which contains a subtle bug for anyone who blindly copies and pastes the code into their programs.
Book Plug
My love-hate relationship with recursion led me to write The Recursive Book of Recursion. It's a wonderful but often overrated technique, and I am quite vocal that I think it's intimidating reputation comes from it being poorly taught more than an inherent difficulty.
The book has code in Python and JavaScript, and is free to read online. I also have a large collection of recursive code examples in Python, including Python programs that use the Turtle module to draw beautiful fractals including your own custom fractals.
I've given talks on recursion at PyCon conferences (also on pyvideo.org), if you want a 30 minute crash course on the subject.
