recursion.md

Recursion

Recursion is when a function calls itself. This requires at least O(n) memory usage for the stack storing the function calls. Here is a great explanation of stack usage in recursive functions.

Code Example

def factorial(n):
	if n <= 1:
		return 1
	return n * factorial(n - 1)

Memoization

Memoization is often useful in recursion. This is when the results of a function call are remembered so they can be used again in later function calls. This is like caching your results to use again.

Code Example

factorial_memo = {}

def factorial(n):
	if n <= 1:
		return 1
	elif n not in factorial_memo:
		factorial_memo[n] = n * factorial(n-1)
	return factorial_memo[n]

Tail Recursion

Tail recursion is where calculations are performed first and then the recursive call is executed. Some programming languages, usually functional ones, optimize tail calls so they take up less room on the call stack.

def factorial(n, running_total=1):
	if n <= 1:
		return running_total
	return factorial(n-1, n * running_total)

Practice Problems

Problem	My Solution
See how many ways given coins can add up to a sum*	https://github.com/aspittel/coding_problems/blob/master/recursion/coin_change.py
See how many ways someone can walk up stairs	https://github.com/aspittel/coding_problems/blob/master/recursion/davis_staircase.py
Calculate a factorial	https://github.com/aspittel/coding_problems/blob/master/recursion/factorial.py
Generate the nth number in the fibonacci sequence	https://github.com/aspittel/coding_problems/blob/master/recursion/fibonacci_numbers.py
Find the number of ways numbers to the nth power can add up to a given number	https://github.com/aspittel/coding_problems/blob/master/recursion/possible_powers.py
Add the digits of a number until there is only one digit left	https://github.com/aspittel/coding_problems/blob/master/recursion/super_sum_digits.py
Calculate how fast an advertisement goes viral	https://github.com/aspittel/coding_problems/blob/master/recursion/viral_advertising.py

*My solution was not recursive, but this is a typical recursion problem