A computer program consists of line-by-line instructions. The computer performs those instructions line-by-line. However, some instructions may be repetitive with a common pattern. Recursion or iteration helps one to write a few lines of codes to perform such repetitive tasks. Suppose a Python list with five-string elements. We wish to print the elements one in a line. This operation needs five lines of codes.
flowers = ['lily', 'tulip', 'rose', 'lavender', 'dandelion'] print(flowers[0]) print(flowers[1]) print(flowers[2]) print(flowers[3]) print(flowers[4])
Output:
It can be observed that the five lines of codes follow the same pattern. The only difference in each line is the index of the list elements. What if this list contains 100 or 1000 elements? Coding will become a tedious task. These kinds of problems are resolved through either iteration or recursion. Here, the iterative form of the above codes is as follows.
for flower in flowers: print(flower)
Output:
These two lines are sufficient to achieve the task even if the list contains a million elements!
Recursion in Python
Recursion is a functional approach of breaking down a problem into a set of simple subproblems with an identical pattern and solving them by calling one subproblem inside another in sequential order. Recursion is executed by defining a function that can solve one subproblem at a time. Somewhere inside that function, it calls itself but solving another subproblem. Thus, the call to itself continues until some limiting criteria is met.
The first call to a recursive function from the main program will be returned only after all the subcalls are finished. Hence, Python stores the results of all subproblems in temporary memory, executes some arithmetic operations (if needed), and releases the memory after the end of recursion.
Iteration in Python
Iterations are performed through ‘for’ and ‘while’ loops. Iterations execute a set of instructions repeatedly until some limiting criteria is met. In contrast to recursion, iteration does not require temporary memory to keep on the results of each iteration. Rather, programmers should define a variable (a number, or list, or string, or any mutable data type) well before the start of iterative calls to collect the results (if there are such arithmetic results) during each iteration.
Further, an iterative task can be accomplished by either a ‘for’ loop or a ‘while’ loop. A ‘for’ loop iterates over a sequence (such as a list, string, tuple and range). It terminates the loop when there is no element left in the sequence. It automatically traverses through the successive elements. But a ‘while’ loop needs initialization of an iterator and manual incrementation of the same. A ‘while’ loop is executed until an iterator-based condition is satisfied.
Recursion vs Iteration
Since Python does not store anything about previous iteration steps, iteration is quite faster and memory-efficient than recursion. In practice, almost all iterations can be performed by recursions and vice-versa. Some tasks can be executed by recursion simpler than iteration due to repeatedly calling the same function. On the other hand, some tasks can be executed by iteration in an elegant way rather than recursion. In terms of time complexity and memory constraints, iteration is preferred over recursion. Both recursion and ‘while’ loops in iteration may result in the dangerous infinite calls situation. If the limiting criteria are not met, a while loop or a recursive function will never converge and lead to a break in program execution.
Since recursion is executed by defining a function, this function can be called whenever required anywhere in the program. Iterative codes must be constructed at the place requirement. Nevertheless, an iterative code set can be generalized by declaring inside a typical Python function (not a recursive function).
The following examples will give a better understanding of recursive and iterative programming approaches.
Factorial of an Integer
Calculating factorial is a popular use case to understand iteration and recursion. For instance, we wish to calculate the factorial of 10. It can be determined as 1*2*3*4*5*6*7*8*9*10 = 3628800. This can be viewed as 10 subproblems of multiplying an incrementing integer to a final result.
# using a for loop n = 10 result = 1 for i in range(1,n+1): result *= i print(result)
Output:
A range function is implemented in a ‘for’ loop since it requires a sequence to iterate over. Range function supplies values iteratively from 1 through 10, one at a time. It stops iteration when the range function stops supplying values(i.e., at 10).
# using a while loop n = 10 result = 1 i = 1 while i <= n: result *= i i += 1 print(result)
Output:
In a ‘while’ loop, an iterator i is introduced and incremented through every loop. While loop stops iterating when the value of i exceeds the integer 10.
# using recursion def Factorial(n): # declare a base case (a limiting criteria) if n == 1: return 1 # continue with general case else: return n * Factorial(n-1) print(Factorial(10))
Output:
A recursive function, named Factorial(), is defined with the limiting criteria of n=1. It first attempts to find the factorial of 10. Factorial(10) is broken down into 10 * Factorial(9). Further, Factorial(9) is broken down into 9 * Factorial(8), and so on. When Factorial(1) is called, it stops the recursion.
Factorial(10) awaits for the value of Factorial(9). Factorial(9) awaits for the value of Factorial(8), and so on. Thus once the limiting criteria (here, n=1) is reached, it starts returning the values.
Reverse a String
A string or a sequence can be reversed through iteration or recursion. Here, we define a function that takes a string and returns its reversed form through an iterative approach. This function can be called any number of times with different strings each time.
def Reverse_iter(s):
rev = ''
for k in s:
rev = k + rev
return rev
Reverse_iter('Welcome!')
Output:
The same task is performed through a recursive approach as follows.
def Reverse_rec(s):
if not s:
return ''
else:
return Reverse_rec(s[1:]) + s[0]
Reverse_rec('Welcome!')
Output:
Build a Triangle with Numbers
Build a triangle of numbers by printing 1 on the first line, 1 thousand on the second line, 1 million on the third line and so on, until a prescribed number of lines. After constructing the lengthy line, decrease the number of digits in descending order. The total number of lines printed would be equal to 2n+1, where n is the input number.
# Iterative form n = 8 # rise up for i in range(n): print(10**(3*i)) # fall down for i in range(n, -1, -1): print(10**(3*i))
Output:
In the above construction, the first loop printed the ascending sequence, and the second loop printed the descending sequence. The same can be implemented with a recursive function as follows.
# recursive form def Triangle(n, i=0): if n==0: print(1) return None print(10**(3*i)) if i<n: # raise up Triangle(n, i+1) else: # fall down Triangle(n-1, i-1) Triangle(8)
Output:
Though the same results are obtained through both iterative and recursive approaches, the recursive approach takes a tough path while the iterative approach follows a straightforward path. This is the kind of problem in which the recursive approach is highly discouraged. However, understanding recursion with this kind of simple problem may help one understand advanced algorithms that rely heavily on recursions, such as backtracking and dynamic programming.
Quicksort
Quicksort is a famous algorithm that sorts the given list or array in place. Actually, Python’s sort() method follows this algorithm for sorting. Merge sort, and Insertion sort are other famous sorting algorithms. Quicksort employs both recursive and iterative approaches to perform the sorting operation quickly and effectively.
Quicksort initially selects the first element of the array as its pivot element. It compares the pivot element with the successive elements iteratively and makes a shift if the right element is higher than the left one. Thus, at the end of the iteration, the pivot element has smaller elements on its left and larger elements on the right. However, both the left side elements and right side elements remain unsorted. The array is now broken into two parts based on the pivot element. The left array and right array are sorted recursively using the Quicksort() function.
def Quicksort(a, l, r): # consider the left most as pivot element current = l+1 # base case (as limiting criteria) if r <= current: return None for i in range(l+1, r): # compare pivot element and shift current's postion if a[l] >= a[i]: a[i], a[current] = a[current], a[i] current += 1 # exchange pivot element and current-but-one element a[l], a[current-1] = a[current-1], a[l] # perform Quicksort before current element Quicksort(a, l, current-1) # perform Quicksort after current element Quicksort(a, current, r) return None
Check how it works.
a = [5,6,4,12,9,2,1,7,6,3]
print('Before sorting...')
print(a)
Quicksort(a, 0, len(a))
print('\nAfter sorting...')
print(a)
Output:
Without recursion, this Quicksort implementation will be a laborious one.
The Google Colab notebook with the above code implementation.
Wrapping Up
In this article, we have discussed the iterative and recursive approaches of Python programming with a few examples. We have discussed the constraints and limitations of both approaches. Finally, we have discussed the famous Quicksort algorithm that incorporates both the iterative and recursive paradigms to perform array sorting. Interested readers can refer to other sorting algorithms, heap, binary search, dynamic programming and backtracking algorithms to learn how recursions and iterations are effectively chosen for a particular task.
