How a recursive algorithm makes a program effective

Key takeaways:

  • Recursive algorithms simplify complex problems by breaking them into smaller subproblems.

  • They improve code clarity and reduce redundancy, especially for tasks like tree traversal.

  • While recursion is clean and concise, it requires careful use due to high space complexity.

  • Choosing between iterative and recursive solutions depends on the problem’s requirements.

What is a recursive algorithm?

A recursive algorithm repeatedly calls itself to solve smaller subproblems until a base condition is met. It is particularly helpful when iterative solutions become overly complex, enabling more streamlined and understandable code.

Advantages of using the recursive approach

The recursive approach has the following advantages:

  • It adds clarity to our code and reduces confusion.
  • It removes redundancy and reduces code length.
  • It saves from iterative code that might cause ambiguity.
  • It’s very useful in the tree traversal. We can reduce the lengthy code of the iterative approach to a shorter one.

Iterative vs. recursive approach

Here’s an example comparing iterative and recursive methods for an inorder traversalA traversing order in which we first print the left child, root, and then the right child. traversal of a BST.

/* Iterative function */
void inOrder(struct Node *root)
{
    stack<Node *> nodeStack;
    Node *currentNode = root;
 
    while (currentNode != NULL || nodeStack.empty() == false)
    {
        /* This while loop gets the left most node
            of the tree */
        while (currentNode !=  NULL)
        {
            nodeStack.push(currentNode);
            currentNode = currentNode->left;
        }
 
        /* After traversing the left subtree, currentNode
           must be NULL at this point */
        currentNode = nodeStack.top();
        nodeStack.pop();
 
        cout << currentNode->data << " ";
 
        /* Till this point, we have visited the node
            and its left subtree */
        currentNode = currentNode->right;
 
    } /* end of while */
} //end of inOrder function.

Code explanation

The above code snippet is the iterative approach for traversing a BST in an inorder manner. Let’s dive into the above function step-by-step:

  • Line 2: Function takes in a pointer to the root node of a tree.

  • Line 4: We create a stack that holds the pointers of type Node.

  • Line 5: We declare another pointer variable currentNode of Node type and point to the root.

  • Lines 7 to 28: We define a while loop that checks two conditions with ||. This loop keeps executing until either of the conditions remains true.

  • Lines 11–15: We define another while loop, which checks the currentNode and keeps executing until it becomes NULL. Inside this loop, line 13 pushes the currentNode onto the stack, and line 14 moves the currentNode pointer to its left node. This while loop traverses the left subtree and terminates the execution when currentNode becomes NULL.

  • Line 19: After traversing the left subtree, we return the top value on the stack and store it in currentNode.

  • Line 20: This removes it from the stack.

  • Line 22: We print the data of the currentNode to the console.

At this stage, the right child is not yet traversed, and line 26 does this. Remember, we are still in the while loop, so the process will continue on the right subtree.

Now, let’s see the same functionality with the recursive approach.

/* A recursive function to print Inorder of a 
   binary tree*/
void inOrder(struct Node* node)
{
    if (node == NULL)
        return;
 
    /* traversing left subtree of a node */
    inOrder(node->left);
 
    /* then print the data of node */
    cout << node->data << " ";
 
    /* traversing right subtree of a node */
    inOrder(node->right);
}

Code explanation

  • Line 3: The function inOrder is declared, taking a pointer to a Node as its parameter. This pointer represents the current node being processed in the traversal.

  • Line 5–6: This is the base case of the recursion. If the node is NULL, it means there is no further subtree to traverse, so the function exits without doing anything. This prevents unnecessary recursive calls and ensures the traversal stops at leaf nodes.

  • Line 9: This recursive call processes the left subtree of the current node. The traversal first dives into the leftmost nodes of the tree, as dictated by the in-order traversal pattern (left, root, right).

  • Line 12: After completing the traversal of the left subtree, the function processes the current node by printing its data. This is the “visit” step of the inorder traversal.

  • Line 15: Finally, the function makes a recursive call to process the right subtree of the current node, completing the in-order traversal pattern.

Key differences

  • Recursion eliminates explicit stack usage and nested loops.

  • The recursive code is significantly cleaner and more concise, improving maintainability.

Use recursion wisely

While recursion is elegant, it has limitations:

  1. High space complexity: Each recursive call uses stack memory until the base condition is met.

  2. Risk of stack overflow: Large inputs can exhaust stack space.

Tip: Use recursion when clarity and simplicity outweigh space concerns. Iterative solutions might be better for cases with massive input sizes or strict performance constraints.

What’s next?

Recursion is a powerful tool in programming that simplifies solving complex problems by breaking them into smaller, manageable subproblems. While it offers clarity and elegance, understanding its limitations—such as increased space complexity—is essential for effective use. Whether you’re navigating tree traversal, dynamic programming, or backtracking problems, mastering recursion will significantly enhance your problem-solving skills and coding efficiency.

If you’re eager to deepen your knowledge and strengthen your coding interview preparation, consider exploring these recommended courses:

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is recursion in programming?

Recursion is a method where a function calls itself to solve a problem by dividing it into smaller subproblems.

Why is recursion better than iteration in some cases?

Recursion simplifies repetitive problems, like traversals or divide-and-conquer algorithms, making code more readable.

When should recursion be avoided?

Avoid recursion for problems requiring deep call stacks or when iterative solutions offer better performance and lower space complexity.

How does recursion affect space complexity?

Recursion uses stack memory for each call, increasing space complexity. It’s crucial to consider this for large datasets.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved