Loops or Recursion: what are the differences?

Recursion is an exciting concept in computer science. Unlike popular opinions, it is not a data structure nor an algorithm. It is a concept. The idea of recursion is quite similar to that of loops and iterations - although not entirely. This incompleteness makes the concept of recursion a confusing subject amongst programmers.

When writing computer code using loops, we work sequentially, having a start and endpoint. With recursion, this linear process doesn’t work.

What is recursion?

Loops are the most fundamental tool in programming, recursion is similar in nature, but much less understood. The simplest definition of a recursive function is a function or sub-function that calls itself. Recursion is a way of writing complex codes. It breaks down problems into sub-problems which it further fragments into even more sub-problems - a continuous loop of problems.

Recursion uses a method that calls itself using an “if-else” statement with recursive calls to create the repetition.

A simple way to look at recursion is like looking at yourself in a mirrored hall. Each mirror reflects you and the reflection of the mirror behind you, in front of you, or beside you. There are also the collective reflection of you and all these mirrors, and so on to infinity.
Another classic recursion is the Matryoshka dolls, also called babushka dolls, stacking dolls, nesting dolls, or Russian dolls. A set of such dolls is designed, so they each fit inside each other. Each consecutive doll is smaller than the one it fits. When a person opens one doll, he finds another doll inside. When they open that one, there’s another inside, even smaller. It goes till we get to the tiniest doll, and there is no smaller one that can be put inside it.

As a function that calls itself, the simplest way to write a recursive function should look like this:

def recursion()
  recursion()

This string raises an error, and we get:

Error [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

While our code is correct, we had a runtime error where the recursion code takes up all the memory – also called a stackoverflow error.

Working with recursion

To understand recursion, we should first look at stack data structure. Stack is a data structure that implements FILO (First In, Last Out) system. The first item in the stack is the last out. Like a game of stacked cards where the first card on the stack is the last taken out.
The two primary operations on a stack involve taking away an item from the top of the pile and adding it. In programming terms, we label these functions as popping and pushing.

Let’s say we have five cards to be stacked and removed. We add the five cards starting with card one and remove them starting with card five. Below is a diagram that illustrates this:

NB: We will be using Python for our code

#recursive function written in python
def card1():
  print('Enter card one')
  card2()
  print('Exit card one')
    
def card2():
  print('Enter card two')
  card3()
  print('Exit card two')
    
def card3():
  print('Enter card three')
  card4()
  print('Exit card three')
    
def card4():
  print('Enter card four')
  card5()
  print('Exit card four')
 
def card5():
  print('Enter card five')
  print('Exit card five')
 
card1()

Output

#output 
Enter card one
Enter card two
Enter card three
Enter card four
Enter card five
Exit card five
Exit card four
Exit card three
Exit card two
Exit card one

We will look at two mathematical concepts covering recursion and how we can implement them using recursion and loops.

1. Factorials

Factorial is an excellent and widespread example of recursion. It is a mathematical concept where the product of all positive integers less than or equal to a given positive integer and denoted by that integer and an exclamation point.

3 factorial, written as 3! is

3 x 2 x 1 = 6

8! is 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40320

To calculate the factorial of a number, we need to multiply that number and all the numbers before it, minus 0. 8! Is the same as 8x7!. Using the total of each singular calculation to multiply with the next digit gives factorial its recursiveness.

Using Python, we can write this recursion like this:

def factorial(no):
  return no * factorial(no - 1)
    
print(factorial(8))

Once again, this returns a recursion error. Rather than stop at 1 for the calculation, the recursion takes it further by calculating 0 and negative integers. So we have:

8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0 x -1 x -2 …

This uses up all the memory as it goes on to infinity, and it brings us to an essential action in recursion - having a base case.

The base case is the case that sets the standard for the recursion. It is the only input to provide an explicit example and answer for the recursion program to follow. With a base case, we teach the computer how to solve the recursion problem using the formula we give it; then, it solves the rest of the problem.
The base is essential because it is also the STOP point of the recursion. Once the program gets to the base case, it knows it has to stop the recursion. It prevents the program from eating up all the memory space and running into a stackoverflow or recursion error during runtime.
Every recursion must have a base case and a recursive function. The recursive function is the case that solves the rest of the problem using the example provided by the base case.

Steps to writing a recursive function

1. Decide your base case
2. Define the function
3. Make the function call inside the function

Using the above steps, we will write the factorial recursive program using “1” as the base case since it is the stop point of the program.

# a recursive function to get the factorial of a number
def factorial(no):
  #base case
  if no == 1:     # 1! is 1
    return 1
  #recusive case
    return no * factorial(no - 1)
    
print(factorial(8))
# output: 40320

2. Fibonacci sequence

The formula is F₀ = F, F₁ = 1,

and

F_n = F_n - 1 + F_n - 2

for n > 1.

Why is Fibonacci considered recursive? Each number in the sequence is added to the number preceding it. The sum of two adjacent numbers becomes the number after it, which, when added to the number before it, forms the following number, and so on.

For example, we can have this, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

0+1 is 1, 1+1 is 2, 2+1 is 3, 3 +2 is 5, 5+3 is 8 and the sequence goes on.

Their positions goes thus: F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5...

Using the formula above, we can say

F(n) = f(n-1) + f(n-2)

F(1) + F(2) = 1

# recursive function for a Fibonacci sequence
def fibonacci(no):
  #setting our base case
  # we use 0 because we don't want to have a value lower than 0
  if no < 0:
    print("Try again with a value higher than 0")
 
  # Check if n is 0
  # then it will return 0
  elif no == 0:
    return 0
 
  # setting up our recursive case
  elif no == 1 or no == 2:
    return 1
 
  else:             
    return fibonacci(no-1) + fibonacci(no-2)
 
print(fibonacci(10))

# output 55
# this prints the total of 0,1,1,2,3,5,8,13,21,34

Another way is to print the sequence, rather than the total

# recursive function for a fibonacci sequence
def fibonacci(no):  
  #the base case
  if no <= 1:  
    return no  
  else:  
    return(fibonacci(no-1) + fibonacci(no-2))  

length = int(input("Length of the sequence "))  # takes input from the user
  
if length <= 0:  
  print("Please enter a number greater than zero")  
else:  
  print("Fibonacci sequence:")  
  for i in range(length):  
    print(fibonacci(i)) 

#output
#Length of the sequence 10
#Fibonacci sequence:
0,1,1,2,3,5,8,13,21,34

How is recursion different from loops?

Loops are similar yet different from recursion. Loops iterate repetitively over an object, list, or data structure until a specific condition(s) are met. Although it can repeat from the beginning to the end of a list, it can also have a starting point and an ending point.

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for a in numbers:
  print (a)
# 1,2,3,4,5,6,7,8,9,10

Loops use control statements like break and continue to alter their sequence. A break statement terminates it while it continues to skip over the loop.

# using break to end a loop
numbers = [1,2,3,4,5,6,7,8,9,10]
for a in numbers:
  if a == 5:
    break
  print(a)

print("Loop stops when it gets to 5")

Factorial and Fibonacci using loops

We used recursion to get the factorial of a number and the Fibonacci sequence of a term. Let’s see how we can get these with loops.

# getting the factorial of a number using loop and iteration
def factorial(no):
  a = 1
  for number in range(1, no + 1):
    a *= number
  return a
    
print(factorial(8))
#40320

For this, we need a counter and a working value or parameter. The counter increases by one step, which is no+1, and the working value is 1. Each time the counter increases, it multiplies by the operating parameter, which is “8” until it executes the condition.

# Fibonacci sequence with iteration
#the length of the sequence
length = int(input("What is the length of the sequence? "))

# first two terms
no1 = 0
no2 = 1
count = 0

# to get a valid number less than or equal to 0
if length <= 0:
  # error text if value is not up to 0
  print("Please enter a value higher than 0")
else:
  # text if the condition is met
  print("Fibonacci sequence:")
  while count < length:
    print(no1)
    nth = no1 + no2
       
    # the sequence
    no1 = no2
    no2 = nth
    count += 1

#output
What is the length of the sequence? 10
Fibonacci sequence:
0
1
1
2
3
5
8
13
21
34

Differences between a loop and a recursion

• Loops do not need to have a base case and a function case. They also do not call themselves.
• Loop uses repetition to go over sequential data, while recursion uses a selection structure.
• Loops take up less memory space and processor time than recursion
• Loops stop when a condition is met; recursion stops when it reaches the base case
• Loop codes are pretty longer than recursion
• Loops are faster than recursions

Recursion has a significant advantage over loops. Any problem we can solve with a loop, we can also solve with recursion. However, not all recursion-solvable issues will work with loops.

Why is recursion not commonly used?

It makes sense to want to use recursion more since they can solve problems loops cannot solve. The disadvantages of using recursion outweigh the one-up recursion has over loops. Here are some reasons why recursion is problematic in coding.

• They are inefficient and take up too much memory
• They are harder to debug
• Recursion could lead to many problems if not correctly written and defined, including runtime errors like stackoverflow and recursion errors.
• They are generally slow

When should recursion be used?

• When a problem:
• has a tree-like structure
• requires backtracking
• has multiple sub problems

Advantages of recursion

• Generating sequence with recursion is more accessible than with nested iterations
• The code is generally shorter.
• Unlike loops, there is no need for multiple functions
• Solves problems outside the jurisdiction of loops

Conclusion

It is tempting to want to use recursion for many problems when you get acquainted with it. Recursion works well and can be used in instances when loops are not efficient. But it is not practical to use recursion unless necessary. It takes up too much memory and can make a code unreadable. Unless necessary, it is best to use loops or dynamic programming before recursion.

For more tips on mastering Programming, please check further articles here.