# Memoization

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


## Example in python
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:
```python
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:
```python
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.


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