Recursion, how it can be used and compares to an iterative approach. (2.2.1)
- 20p13280
- Oct 22, 2025
- 4 min read
Updated: Nov 24, 2025
This post covers the following from the specification (2.2.1):
(a) Programming constructs: sequence, iteration, branching.
(b) Recursion, how it can be used and compares to an iterative approach.
(c) Global and local variables.
(d) Modularity, functions and procedures, parameter passing by value and by reference.
(e) Use of an IDE to develop/debug a program.
(f) Use of object oriented techniques. (Skipped for now)
What is recursion?
Recursion is where you call the function that's currently executing from the funcion that's currently executing.
Algorithm to find factorial for any n (n!):
You can represent 5! as 5*4! and 4! as 4*3! and etc.
function getFactorial(n)
if n < 2, return 1
else return n * getFactorial(n-1)This re-runs itself, and once n is 1 or lower it returns 1 since 1! = 1 and 0! is 1.
An issue of recursion is that you can run out of memory if there are loads of calls. For example finding the factorial of 1,000,000 would use over 1,000,000 calls and each call creates a local variable and also they are open function calls so the local variables won't be destroyed yet since the subroutine hasn't finished executing.
Recursion doesn't scale up like iteration does because of the large memory overhead.
Also within many languages an iterative solution is typically better, and more efficient.
Using recursion can also make code harder to read/understand compared to an iterative solution so it makes the code harder to maintain. They become "more abstract". (More on this further down after the Call Stack explination)
However in some cases they are extremely fast and easy to code so they are practical in cases, like a binary search or binary trees. A tree is a node that has branches that leads to more nodes and then from there those nodes have branches that go to more nodes and it continues. The fibinachi sequence creates a tree due to its recursive nature and how it works as it needs the previous 2 numbers.
A base case is a basically the stopping condition. For most programs this would be function(1), where 1 is the base case. This is applicable in examples like factorial and fibonacci.
Recursive functions aren't always needed, you can do everything that you can do with recursion with iteration. However one may be more complicated than the other, for example the fibbonachi sequence or factorial and so recursion is better for readabilty and maintainability.
Stack & Call-Stack
A stack is a simple data structure that holds a sequence of data and only lets you interact with the topmost item. It's refered to as a FILO datastore (First In, Last Out)
You can only add and remove from a stack. Adding to the top of a stack is called pushing, removing from the top of the stack is called popping.
Python lists can be an example of a stack if you only use append() and pop().
A call stack is a stack of "frame objects", where a frame object represented is a function call. Python handles the call stack automatically, there are built-in modules to interface with this called inspect and traceback. Once a function call is made, a "frame" is added to the call stack, once completed and returns it's popped from the call stack.
A stack overflow/recursion error is an error where you run a recursive function too many times. Python puts a limit to give a recursion error. Since items are added to the call stack, once the subroutine has been called by itself too many times the system will run out of memory causing a stack overflow error.
Caching can be used in iteration to cache values from specific inputs so that they won't have to be constatly called and called and adding loads of calls to the call stack that have already been executed before. This process is called memoization. Within Python there are 2 common ways to do this, the first is storing parameters to values within a dictionary. The other way (which is in-built to python) is using a module called functools and it's decorator lru_cache, with LRU standing for Least Recently Used Cache. This will make it cleaner to cache values.
Tail Call Optimisation/Elimination is where the recursive function call is the last thing in the function call before it returns, this means that all the local variables are destroyed and don't take up more memory so that a stack overflow error requires more recursive calls before happening since less memory is used up on each call.
Tail Call Optimisation is a compiler trick, but the CPython (most common python interpreter) doesn't and will never implement Tail Call Optimisation. It's been quoted as "unpythonic".
The tower of hanoi is a good example of recursion. Where you move the n-1 disk along, so if there are 3 disks, the first on goes to position 3, then the second to position 2, then the position 3 one to position 2. Then it loops moving position 1 to 3, then the top of 2 to 1 then 2 to 3 then 1 to 3. This is using recursion by parsing in the value of n-1 on each of the recursive calls. The middle one(s) are known as a(n) auxillery node(s).
Recursion vs Iteration
Compared to the recursive aproach, iterative is more memory efficient. However the iterative approach can be less readable than a recursive approach and this is a reason that many programmers decide to use recursion. Due to the lower memory consumptoin, this is why an interative solution typically scales better for larger inputs.
All recursive solutions can be re-wrote to use an iterative approach, and the same goes for all iterative solutions.
Iteration is less stack-heavy too, only having one item on the stack at a time compared to recursion which has n stack items where n is the input amount (e.g. fibbonachi of 8th position gives 8 stack items).
Recursion can't do infinate loops as it will cause a stack-overflow due to the large amount of stack items, whereas with iteration it can do an infinate loop as it only has one item on the call-stack at a time.
Both recursion and iteration share a simular principle using either a control statement or a base-case which cause the stopping of the repeating code, a base case starts the chain of ending function calls whereas iteration when the coontrol statement isnt met just removes the one call-stack item and stops.
By nature iteration is faster than recursion, and also has no overhead.
SOURCES
test
I opine that this is an incredible read!
A stellar read! Quite promiscuous and intriguing! I will be alerting all my fellow students of this wonderous resource you have created!