The Power of Recursion: A Technique for Solving Complex Problems
This article will explore the fundamentals of recursion, including how it works, its most useful applications, and some typical examples of recursive algorithms.
Recursion is a technique used to solve complicated problems in computer science and mathematics by breaking them down into simpler problems that can be solved recursively. The basic concept behind recursion is to call a function within itself, with each recursive call solving a smaller sub-problem until a base case is reached. The advantage of recursion lies in its ability to solve complex problems that might be difficult to solve using traditional methods. It also allows for more elegant and efficient solutions and can improve code readability and maintainability.
History of Recursion
Recursion is a fundamental concept in computer science and mathematics that refers to a function or procedure that calls itself directly or indirectly. It is a powerful tool for solving problems that involve repetitive or hierarchical structures, such as trees or graphs. The idea of recursion has been around for centuries and can be traced back to ancient Greek and Indian mathematics. The Greek mathematician Euclid used recursive definition to construct his famous algorithm for finding the greatest common divisor of two numbers.
In India, the mathematician Pingala used recursion in his work on Sanskrit poetry, where he developed a system for describing the meter of poetic verse using recursive rules. In the 19th century, the German mathematician Georg Cantor used recursion to develop his theory of infinite sets, which became the foundation of modern set theory.
The logician and philosopher Gottlob Frege also explored the concept of recursion who used recursive functions to define the natural numbers. In the mid-20th century, recursion became a key concept in computer science with the development of high-level programming languages. The first programming language to support recursion was Lisp, developed in the late 1950s. Recursion quickly became an important tool for solving problems in computer science, and it is now a standard feature in most programming languages. Today, recursion is used in various fields, from artificial intelligence and machine learning to bioinformatics and data science. It is a powerful and versatile tool that has revolutionized how we approach complex problems in science and technology.
Best-suited Programming courses for you
Learn Programming with these high-rated online courses
How Recursion Works
Recursion is a technique that relies on the function calling itself repeatedly until a base case is reached. The base case is a special case that can be solved without recursion, and it is the case that stops the recursion.
The general structure of a recursive function is as follows:
def recursive_function(input):
# Base case(s)
if <input meets some condition>:
return <some value>
# Recursive case
else:
# Break down the problem into smaller sub-problems
subproblem = <break down input into smaller sub-problems>
# Solve each sub-problem recursively
result = recursive_function(subproblem)
# Combine the results of the sub-problems
output = <combine the results>
return output
Source : DEV Community
This method involves checking if the current problem is the base case in a function. If it is, the solution for the base case is returned. If it is not, the parameters are modified and the function calls itself recursively with the updated parameters. The function then combines the solution for the current problem with the result of the recursive call to solve the original problem. As an example, let’s consider computing the factorial of a non-negative integer n. The factorial of n is the product of all positive integers less than or equal to n. For instance, the factorial of 5 is 5 * 4 * 3 * 2 * 1 = 120. To solve this problem recursively, we would need to create a function that checks if the current problem is the base case. If not, it modifies the parameters and calls itself recursively until it reaches the base case. Finally, the function combines the solution for the current problem with the result of the recursive call to solve the original problem.
def factorial(n): if n==0: return 1 else: return n*factorial(n-1)
print(f"Factorial of 5 is {factorial(5)}")
# output # Factorial of 5 is 120
This recursive function calculates the factorial of a non-negative integer. The base case occurs when n is equal to 0, and in this case, the function returns 1. Otherwise, it returns n multiplied by the factorial of (n – 1). This recursive call is repeated until the base case is reached.
When to use Recursion
Recursion can be an elegant and efficient solution to complex problems, but it is not always the best approach. It’s crucial to consider several factors when deciding whether to use recursion. One of them is whether the problem can be divided into smaller sub-problems that can be solved recursively. It’s also important to define a well-defined base case, as a missing base case can cause infinite recursion and a stack overflow error. Additionally, it’s necessary to determine whether recursion is efficient for the given problem, and if the problem can be solved using a divide-and-conquer approach, recursion may be a viable solution.
Common Examples of Recursive Algorithms
Recursive algorithms are widely used in computer science and mathematics to solve complex problems. Here are some examples of well-known recursive algorithms: Fibonacci Sequence: The Fibonacci sequence is a sequence of numbers in which each number is the sum of the two preceding numbers. The sequence starts with 0 and 1, and the first few numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, and so on.
A recursive solution to compute the nth number in the Fibonacci sequence is:
def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n - 1) + fibonacci(n - 2)
print(f"8th term in Fibonacci Sequence is {fibonacci(8)}")
# output -> 8th term in Fibonacci Sequence is 21
This function computes the nth Fibonacci number by recursively computing the (n-1)th and (n-2)th Fibonacci numbers until the base case of n=0 or n=1 is reached.
Binary Search
A Binary search algorithm is often used to search for a specific element in a sorted array. The algorithm works by repeatedly dividing the array in half until the element is found or it is determined that the element is not in the array.
Here’s an example of a recursive implementation of binary search in Python:
def binary_search(arr, start, end, x): if end >= start: mid = start + (end - start) // 2 if arr[mid] == x: return mid elif arr[mid] > x: return binary_search(arr, start, mid - 1, x) else: return binary_search(arr, mid + 1, end, x) else: return -1
arr = [1,2,3,4,5]print(f"Element found at index {binary_search(arr,0,len(arr)-1,5)}")
#output = Element found at index 4
This function searches the sorted array arr for the element x by recursively dividing the array in half and searching the appropriate sub-array until the element is found or it is determined that the element is not in Factorial of a Number:
def fact(n): if n==0 or n==1: return 1 else: return n*fact(n-1)
n = int(input("Enter a number to find the factorial of it"))print(fact(n))
Source : Stack Overflow
Tower of Hanoi
The Tower of Hanoi puzzle involves moving a set of disks of different sizes from one peg to another, following certain rules. A recursive solution can be used to solve this puzzle by breaking it down into smaller sub-problems. In each recursive call, the function moves a smaller sub-stack of disks to the target peg using the spare peg. This process continues until the base case is reached, which is when there is only one disk to move. Then, the function moves that disk to the target peg. The solution for the original problem is obtained by combining the solutions to the sub-problems.
def tower_of_hanoi(n, source, target, auxiliary): if n == 1: print(f"Move disk 1 from {source} to {target}") return tower_of_hanoi(n-1, source, auxiliary, target) print(f"Move disk {n} from {source} to {target}") tower_of_hanoi(n-1, auxiliary, target, source)
tower_of_hanoi(3, "A", "C", "B")
#output -> # Move disk 1 from A to C# Move disk 2 from A to B# Move disk 1 from C to B# Move disk 3 from A to C# Move disk 1 from B to A# Move disk 2 from B to C# Move disk 1 from A to C
Source : Geeky Codes
This function recursively solves the Tower of Hanoi problem by moving n-1 disks from the source peg to the auxiliary peg, then moving the nth disk from the source peg to the destination peg, and finally moving the n-1 disks from the auxiliary peg to the destination peg.
Here are some examples of recursive algorithms for common data structures:
Binary Search Tree Traversal
Source: Teachics
Binary search trees (STs) are data structures that are commonly used for efficient storage and searching of data. One common operation on BSTs is traversal, which involves visiting all nodes in the tree in a specific order. Recursive algorithms can be used to traverse BSTs in the following orders: Inorder traversal: visits the left subtree, then the current node, then the right subtree. Preorder traversal: visits the current node, then the left subtree, then the right subtree. Postorder traversal: visits the left subtree, then the right subtree, then the current node. Here are some examples of recursive algorithms for each of these traversal orders:
class Node: def __init__(self, val): self.val = val self.left = None self.right = None
def inorder(root): if root is not None: inorder(root.left) print(root.val, end=" ") inorder(root.right)
def postorder(root): if root is not None: postorder(root.left) postorder(root.right) print(root.val, end=" ")
def preorder(root): if root is not None: print(root.val, end=" ") preorder(root.left) preorder(root.right)
# Example usage:root = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)
print("Inorder traversal:")inorder(root)
print("\nPostorder traversal:")postorder(root)
print("\nPreorder traversal:")preorder(root)
#output
# Inorder traversal:# 4 2 5 1 3 # Postorder traversal:# 4 5 2 3 1 # Preorder traversal:# 1 2 4 5 3
Linked List Reversal
Linked lists are a type of data structure consisting of nodes connected to each other by pointers. One common operation on linked lists is reversal, which involves reversing the order of the nodes in the list. A recursive algorithm for linked list reversal is:
class Node: def __init__(self, data): self.data = data self.next = None
class LinkedList: def __init__(self): self.head = None
def append(self, data): new_node = Node(data) if self.head is None: self.head = new_node return current_node = self.head while current_node.next is not None: current_node = current_node.next current_node.next = new_node
def print_list(self): current_node = self.head while current_node is not None: print(current_node.data, end=" ") current_node = current_node.next
def reverse(self): prev_node = None current_node = self.head while current_node is not None: next_node = current_node.next current_node.next = prev_node prev_node = current_node current_node = next_node self.head = prev_node
# Example usage:linked_list = LinkedList()linked_list.append(1)linked_list.append(2)linked_list.append(3)linked_list.append(4)linked_list.append(5)
print("Original list:")linked_list.print_list()
linked_list.reverse()
print("\nReversed list:")linked_list.print_list()
#output# Original list:# 1 2 3 4 5 # Reversed list:# 5 4 3 2 1
This function uses recursion to reverse a linked list by recursively calling itself with the next node as the argument until the end of the list is reached, and then reversing the pointers between the nodes.
Graph Traversal
DFS: A recursive implementation of DFS involves starting at a given node and recursively visiting all adjacent nodes that have not been visited yet. The algorithm can be implemented using a boolean array to keep track of visited nodes.
BFS: A recursive implementation of BFS is less common than an iterative implementation, but it can be done using a queue data structure. The recursive algorithm involves visiting all nodes at a given depth before recursively calling the algorithm on the next depth. The algorithm can also use a boolean array to keep track of visited nodes.
Source: Medium
class Graph: def __init__(self, n): self.adj_list = [[] for _ in range(n)] self.visited = [False] * n
def add_edge(self, u, v): self.adj_list[u].append(v) self.adj_list[v].append(u)
def dfs(self, start): self.visited[start] = True print(start) for neighbor in self.adj_list[start]: if not self.visited[neighbor]: self.dfs(neighbor)
def bfs(self, start): queue = [start] self.visited[start] = True while queue: node = queue.pop(0) print(node) for neighbor in self.adj_list[node]: if not self.visited[neighbor]: queue.append(neighbor) self.visited[neighbor] = True
def main(): # Create a graph with 6 vertices and 7 edges graph = Graph(6) graph.add_edge(0, 1) graph.add_edge(0, 2) graph.add_edge(1, 3) graph.add_edge(2, 3) graph.add_edge(2, 4) graph.add_edge(3, 4) graph.add_edge(3, 5)
# Perform DFS starting from vertex 0 print("DFS traversal:") graph.dfs(0)
# Reset visited array for BFS graph.visited = [False] * 6
# Perform BFS starting from vertex 0 print("BFS traversal:") graph.bfs(0)
if __name__ == "__main__": main()
#output# DFS traversal:# 0# 1# 3# 2# 4# 5# BFS traversal:# 0# 1# 2# 3# 4# 5
Recursion vs Iteration:
Let’s understand Recursion vs Iteration
Working with tree structures allows recursive algorithms to mimic the data’s structure directly, making them more succinct and understandable in many situations. A binary tree’s nodes can be added up using the code below, for instance:
int sum(Node* root) { if (root == NULL) { return 0; } else { return root->val + sum(root->left) + sum(root->right); }}
This recursive approach is easy to read and understand and mirrors the tree’s structure. On the other hand, an iterative solution would require the use of a stack or queue to keep track of nodes, making it more complex. Another example is the famous Fibonacci sequence. The iterative approach requires a loop to calculate the sequence, whereas the recursive approach is more concise and easier to understand:
int fibonacci(int n) { if (n <= 1) { return n; } else { return fibonacci(n-1) + fibonacci(n-2); }}
Recursion can generally be more efficient than iteration when dealing with recursive data structures or when the problem can be naturally expressed recursively. However, it is important to remember that recursive algorithms can be less efficient than iterative ones in some cases, particularly when dealing with large input sizes or deeply nested recursive calls.
Common pitfalls of Recursion:
Infinite Recursion:
One of the most frequent hazards of recursion is infinite recursion, in which a function repeatedly invokes itself without ever reaching the base case. This can cause a stack overflow and cause your software to fail. Always identify a base case and make sure that each recursive call moves you closer to that base case in order to prevent infinite recursion.
Overlapping subproblems: Recursion can also fall victim to overlapping subproblems, when the same subproblem is handled more than once and more calculations are required. This can be particularly troublesome for methods for dynamic programming. You can use memoization or tabulation to store the outcomes of earlier computations in order to prevent overlapping subproblems.
Performance Issues: Recursion may be slower than iterative methods due to the overhead of making function calls and manipulating the stack. This can be particularly challenging for complex recursive calls or huge inputs. You can try to improve the base case and make sure that each recursive call shrinks the size of the problem in order to improve performance.
Some questions for you to solve!
- Write a recursive function to calculate the factorial of a given number.
- Write a recursive function to calculate the nth number in the Fibonacci sequence.
- Write a recursive function to count the number of occurrences of a given character in a string.
- Write a recursive function to check if a given string is a palindrome.
- Write a recursive function to find the greatest common divisor of two numbers.
- Write a recursive function to reverse a given linked list.
- Write a recursive function to find the sum of all elements in a binary tree.
- Write a recursive function to print all possible permutations of a given string.
- Write a recursive function to sort a given array using the quicksort algorithm.
- Write a recursive function to find the maximum element in a given binary tree.
Author – Papireddy Eppala
This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio
Top Picks & New Arrivals
