As we all know recursion and looping can be used interchangeably but one type of problem may lead one to be used. Mathematical formulae are often defined recursively so it is easier to simply ‘copy’ the formulae into code. A common example is the factorial function, like
5! = 120, and this is defined mathematically like:
n! = n * (n - 1) * (n - 2) * .. * 1
But this brings about a problem? Can you see it? If you were to do this for a large number you would be computing the same value many times. Wouldn’t it better if you could ‘memorize’ a value?
You could just use a Python dictionary like:
Python already has this built-in by importing
functools from the standard library. Here’s the Fibonacci algorithm using LRU cache:
This just goes to show it is still possible to write performant functions that are easier to understand than there iterative equivalent.