What is the difference between loops and recursion in Python?

Both loops and recursion are programming concepts we use to solve problems. One may fit a situation better than the other, so knowing when to use which of the two is very important.

For the purposes of this shot, sample pieces of code will be written in Python.

What is a loop?

A loop is an instruction that tells the computer to repeatedly execute an instruction, usually based on a condition. We have three main kinds of loops:

• for loops
• while loops
• do while loops

The latter is not available in Python and is only a little different from regular while loops.

For Loops

For loops are typically used to iterate over a finite number of items and perform an action on an item at a particular period in the loop, e.g., iterating over a list of names and printing them.

In the example below, we iterate over a finite list of names and print each name to the terminal.

names = ["Kyle", "John", "Doe", "Sam"]

for name in names:
    print(name)

While loops

While loops continually execute while a particular condition is true and will only halt/stop when a break statement is encountered or the initial condition becomes false.

number = 0
while (number < 10):
    print(number)

The code above contains a while loop that executes infinitely because number is always equal to zero. Let’s fix this by incrementing the value of number on every iteration.

number = 0
while (number < 10):
    print(number)
    number = number + 1

Now, this code will execute 9 times.

We have a variable number with an initial value of 0.

The condition of the loop is only true only when the value of number is less than 10. We add 1 to the value of number after every iteration.

The loop starts by checking if the value of number is less than 10, which is initially true.

Because this is true, the loop executes its body, prints the value of number, and adds 1 to it. The value of number now equals 1 and the check repeats. 1 is less than 10, so the body executes again and 1 is added to the value of number.

This process continues until the value of number reaches 9. The loop checks if 9 < 10 is true and executes its body, then adds 1 to number, which makes its value 10. The loop proceeds to check if number < 10; this is now false, so the loop stops and the program ends.

Do-while loops

Do-while loops are similar to a normal while loop with a little twist. In this case, the loop will always execute at least once before it begins to check if the condition is satisfied.

As I mentioned earlier, we do not have do-while loops in Python. Below is the structure of a typical do-while loop.

int number = 0

do {
    print(2);
    number = number + 1;
} while (number < 10);

This loop begins by printing 2 and increments number by one before it checks the condition. The loop will therefore print 2 9 times.

Recursion

Recursion is a little similar to loops. Recursion is a situation where a function calls itself in its body during execution. Below is an example of a recursive functiona function that executes itself in its body.

def call_myself():
    call_myself()

If you execute the code above, it will eventually raise a RecursionError that says the max recursion depth is exceeded. You can use a recursive function when you need to solve a complex chain problem by breaking it down and solving smaller instances of it. A common example is calculating factorials or the Fibonacci series.

Loops versus recursion

Let’s use the following situation as an example. Say we want to be able to calculate the factorial of a number given to us. The factorial of a number is given by finding the product of the number and its backward 1 step neighbor repeatedly until we reach 1.

There is no factorial for negative numbers.

The factorial of 5 is given by 5x4x3x2x1, which equals 120.

The factorial of 0 is agreed to be 1.

Let’s write a function that will solve the problem for us.

def factorial(n):
    result = 1
    current_difference = 0
    current_number = 0
    while (current_number < n):
        result *= n-current_difference
        current_number += 1
        current_difference += 1

    return result

In this function, we use a while loop to calculate the factorial of a number. The function can look a little overwhelming, but with recursion, we can save lines and readability by breaking down the problem.

def factorial(n):
    if n == 0 or n == 1:
        return 1

    # otherwise
    return n*factorial(n-1)

The function above is a recursive function that calculates the factorial of a number. If we compare both functions, the latter is more readable and understandable.

Differences between loops and recursion

• Recursion does not need a condition to be satisfied before it can run.

• Recursion has limits to its execution. This is mainly because functions are stored on the Stack Memory, which has a maximum size. A recursive function will continually call itself, pushing values and new instances of the function to the stack, which might eventually lead to a Stack Overflow error.

• In comparison, loops are stored in dynamic memory, where variables can be created indefinitely.

• The execution of a recursive function is relatively slower than loops.

  

• Recursion is generally more readable than loops.

• Recursion is more expensive, computation-wise, compared to loops, but can be sped up with memoization.