Optimisation technique: cache recursive function call results to avoid useless computations

An example problem: you have a staircase with 10 steps and can climb up 1, 3, 5 steps at once. How many combinations are there?

Here, recursion can be used to provide a simple but inefficient implementation:

def countsteps(n, steps):
	if (n == 0):
		return 1
	if (n < 0)
		return 0
	return sum(countsteps(n - step, steps) for step in steps)

It can be observed that this implementation would quickly get too inefficient for higher step counts. An improvement would be to cache the function calls in a dictionary, returning the cached value instead of needlessly recomputing the same recursive function calls:

def countsteps_cached(n, steps, cache):
	if (n == 0):
		return 1
	if (n < 0)
		return 0
	if (n in cache): # return cached function call
		return n
 
	# else, compute and cache
	total = sum(countsteps(n - step, steps) for step in steps)
	cache[n] = total
	return total

Results are computed much quicker compared to the initial implementation.

https://www.youtube.com/watch?v=JXUOMsFBDXQ Computerphile video about the topic