Difference Between Recursion and Iteration

In data structure and algorithms, iteration and recursion are two fundamental problem-solving approaches. Both involve executing instructions repeatedly until the task is finished. But there are significant differences between recursion and iteration in terms of thought processes, implementation approaches, analysis techniques, code complexity, and code performance.

Difference in terms of thought process

Sometimes, a coding problem can be solved using both iteration and recursion, but the choice of approach often depends on the nature of the problem and which one is more intuitive to use.

• For example, recursion is often more natural for algorithms such as binary search, merge sort, quick sort, DFS traversal of a graph, etc. Similarly, approaches like backtracking and data structures like trees are often easier to understand using recursion.
• On the other hand, many coding problems are more straightforward to solve using iteration. Recursive solutions may be challenging or impossible to understand in these cases. For example, insertion sort, heap sort, and BFS traversal of a graph or tree are often more efficiently implemented using iteration.

Ultimately, the decision between iteration and recursion depends on the specific problem being solved and which approach is more intuitive or efficient in that situation.

Difference in terms of implementation approach

Iteration is implemented using a loop, which consists of initialization, increment of loop variables, code inside the loop body, and termination conditions. In contrast, recursion is implemented using function calls and defined in terms of the number of sub-problems, input size of sub-problems, base cases, and additional operations required to combine solutions to the sub-problems.

• In a recursive implementation, compiler uses call stack to store function calls to smaller sub-problems and keep track of the current state of the program.
• It is possible to transform every recursive implementation into an iterative implementation using a stack (which is what the compiler does in the background).
• In most cases, iterative implementation using a stack becomes more complex due to many input variables, additional operations, and complex nature of recursive calls. This means that changing a recursive algorithm to an iterative algorithm may require significant code modification, which can make the code more complicated or less maintainable.
• There are some situations where recursion is simple and can be easily converted into iterative code using a stack. One idea that works well is to mimic what the compiler does. An excellent example of this is iterative DFS traversal using a stack.
• There are some recursive solutions that can be implemented iteratively without using a stack. Classic examples of this include finding Fibonacci numbers, finding the factorial, and binary search.

Difference in terms of code execution

An iterative process involves repeatedly executing some code statements using a loop until the problem is solved. In contrast, a recursive process involves solving the problem using smaller sub-problems until the smallest version of the problem (the base case) is reached.

• Recursion is usually slower due to the extra overhead of calling multiple functions and maintaining the call stack. However, it can be more intuitive and easier to implement sometimes, especially when the problem can be naturally divided into smaller sub-problems.
• Iteration is generally faster due to the lack of function call overhead, but it can be more complex to implement and debug in some cases.

Difference in terms of code error

• In iteration, an infinite loop can occur due to an error in the assignment or increment of the loop variable or a wrong terminating condition. This can consume system resources like processor time or memory and stop the program execution.
• In recursion, an infinite recursion may occur due to the absence of base cases or incorrect base cases. This can cause a stack overflow scenario, leading to a CPU crash.

Both iteration and recursion can be prone to small but critical mistakes, such as the "off by one" error in iteration or passing the wrong value to function parameters in recursion. It is important to carefully consider and test conditions and variables involved in these approaches to avoid such errors.

Difference in terms of code analysis

• In general, the analysis of iterative code is relatively simple as it involves counting the number of loop iterations and multiplying that by the time complexity of the code executed at each iteration. However, there are some exceptions where counting loop iterations can be tricky or the operations performed by the loop are lower than expected.
• The primary method for analyzing recursive code is the recursion tree method, which involves drawing a tree and summing the total cost of the recursion at each level. This can be more difficult due to complex recurrence relations. However, in the case of divide and conquer solutions, it is possible to analyze the code more simply using the master theorem.

Comparing recursion vs iteration using code examples

Here are some examples of recursive and iterative solutions to the same problem, along with a comparison of their thought process, performance, and code simplicity.

Example 1: Finding the factorial of a number

Finding the nth factorial can be implemented using both iterative and recursive approaches. While the recursive solution may appear simpler, it can be slower due to the overhead of function calls and the need for additional space for the call stack.

Both iterative and recursive solutions have a time complexity of O(n), but the recursive solution requires O(n) extra space for the call stack. When choosing between iterative and recursive solutions, this space requirement can be a crucial factor.

Recursive pseudocode

int fact(int n)
{
    if (n == 0)
        return 1
    return n * fact(n - 1)
}

Iterative pseudocode

int fact(int n)
{
    int res = 1
    for (int i = 2; i <= n; i = i + 1)
        res = res * i
    return res
}

Example 2: Finding nth Fibonacci

In this case, the recursive solution for calculating Fibonacci numbers may be simple and easy to understand, but it is highly inefficient, with time complexity of O(2^n) and space complexity of O(n). In contrast, the iterative solution has a time complexity of O(n) and a space complexity of O(1), making it a much more efficient option.

When choosing between iterative and recursive solutions, we need to consider the trade-off between simplicity, time complexity, and space complexity.

Recursive pseudocode

int fib(int n)
{
    if(n <= 1)
        return n
    return fib(n - 1) + fib(n - 2)
}

Iterative pseudocode

int fib(int n)
{
    if (n <= 1 )
       return n
    a = 0, b = 1
    for (int i = 2; i <= n; i = i + 1)
    {
        c = a + b
        a = b
        b = c
    }
    return c
}

Example 3: Binary search

In this case, both the iterative and recursive binary search solutions appear simple. However, the recursive solution may be easier to understand as it involves solving the larger problem using the solution of a smaller problem.

Despite this, iterative solution is a more efficient choice in terms of time and space complexity. Both solutions have a time complexity of O(logn), but the recursive solution requires O(logn) extra space for the call stack. In contrast, the iterative solution has no overhead of recursive calls and requires only O(1) space, making it a more efficient choice.

Recursive pseudocode

int binarySearch(int X[], int l, int r, int key) 
{ 
    if (l > r)
        return -1 
    else    
    { 
        int mid = l + (r - l) / 2
        if (X[mid] == key) 
            return mid
        if (X[mid] > key) 
            return binarySearch(X, l, mid - 1, key)
        else    
            return binarySearch(X, mid + 1, r, key) 
    }
}

Iterative pseudocode

int binarySearch(int X[], int l, int r, int key)
{ 
    while (l <= r) 
    { 
        int mid = l + (r - l) / 2
        if (X[mid] == key) 
            return mid
        if (X[mid] < key) 
            l = mid + 1
        else
            r = mid - 1
    }
    return -1
}

Example 4: Insertion sort

In this case, both iterative and recursive solutions have a time complexity of O(n^2). However, iterative solution is a more efficient choice in terms of space complexity. Recursive solution requires O(n) extra space for the call stack, while the iterative solution has no overhead of recursive calls and requires only O(1) space. So the iterative solution offers a balance of efficiency and simplicity, making it the best choice.

Iterative pseudocode

void insertionSort(int X[], int n)  
{  
    for (int i = 1; i < n; i = i + 1) 
    {  
        int currValue = X[i]
        int j = i - 1  
        while (j >= 0 && X[j] > currValue) 
        {  
            X[j + 1] = X[j]
            j = j - 1 
        }
        X[j + 1] = currValue
    }  
 }   

Recursive pseudocode

void insertionSort(int X[], int n) 
{ 
    if (n <= 1) 
        return
    insertionSort(X, n - 1)
    int temp = X[n - 1]
    int i = n - 2
    while (i >= 0 && X[i] > temp) 
    { 
        X[i + 1] = X[i]
        i = i - 1
    } 
    X[i + 1] = temp
} 

Example 5: Pre-order tree traversal

Here, recursive code is simple and easy to understand because it involves only one function parameter and a few lines of code. On the other hand, recursive code of preorder traversal is tail-recursive i.e. there are no additional operations after the final recursive call. As a result, it can be implemented iteratively using a stack.

In the worst case, both recursive and iterative approaches have a space and time complexity of O(n). It is worth taking the time to understand this iterative code because it can be a useful tool in problem-solving.

Recursive pseudocode

void preorder(TreeNode root) 
{
    if (root == NULL)
        return
    process(root->data)
    preorder(root->left)
    preorder(root->right)
}

Iterative pseudocode

void iterativePreorder(TreeNode root) 
{
    if(root == NULL)
        return
    Stack<TreeNode> treeStack
    TreeNode currNode = root
    TreeNode prevNode = NULL
    while (treeStack.empty() == false || currNode != NULL) 
    {
        if (currNode != NULL)
        {
            process(currNode->data)
            treeStack.push(currNode)
            currNode = currNode->left
        }
        else
        {
            prevNode = treeStack.pop()
            currNode = prevNode->right
        }
    }
}

Critical ideas to think about!

1. Despite being slower in general, why do some people prefer recursion over iteration?
2. Is there a general guideline for converting recursive code into iterative code?
3. Is it possible to convert all recursive code into iterative code or vice versa?

Enjoy learning, Enjoy algorithms!