Recursion vs Iteration

I was always asked about the key differences between the use of recursion vs the use of iteration and that always stumbles me as my answer is always the same, “it depends”. Recursion and Iteration is the act of executing a set of instructions repeatedly.

Recursion

Recursion is a simple method call in which the method being called is the same as the one making the call in the first place.

Iteration

Iteration is when a loop is executed repeatedly until a certain condition is met.

Both Recursion and Iteration will execute until the conditions are met but the difference is that recursion can be more expensive in both memory space and processor time and the overhead of method calls can lead to system crashes, whereas the iteration doesn’t but consumes more CPU cycles.

Let’s see practically the differences between Recursion and Iteration using the classic Fibonacci Sequence.

Using Recursion:

def fibonacci(n):
    """
    Using recursion to get the fibonacci sequence
    """
    if n < 0:
        print("Invalid number")
    elif n == 1:
        return 0
    elif n == 2:
        return 2
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

As you can see, the method being called is the same method calling it in the first place.

Using Iteration:

def fibonacci(n):
    """
    Using iteration to get the Fibonacci Sequence
    """
    fibs = [0, 1]
    for i in range(2, n + 1):
        fibs.append(fibs[-1] + fibs[-2])
    return fibs

Here, as you can see, uses a simple initial given list [0, 1] and loops starting at position 2 and appends to the existing list obtaining the requested list, here uses more CPU cycles but is by far faster than the recursion version, mostly if we try to obtain the fibonacci(500).

Using the second approach we can even ask:

fibonacci(500)[99]: 218922995834555169026

I hope this helps some people clarifying some differences between both approaches and again, all depends on what you want to achieve.