Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

algorithms

How a recursive algorithm makes a program effective

Ayyaz Sheikh

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

A recursive algorithm is defined by the name it calls itself repeatedly. It is beneficial in cases when the iterative solution becomes very complex. We try to separate the code that must be executed multiple times and make it a recursive function.

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 6-7 lines only.

Iterative versus recursive approach

Now, we’ll look at two code snippets. One is the iterative approach for the famous inorder traversalA traversing order in which we first print the left child, root, and then the right child. of BST, and the other one is the recursive approach. We’ll notice a clear difference between both approaches.

/* 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.
Iterative function for inorder traversal

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:

  • 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 means that 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 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 */
printInorder(node->left);
/* then print the data of node */
cout << node->data << " ";
/* traversing right subtree of a node */
printInorder(node->right);
}
Recursive function for inorder traversal

Now, comparing both codes side by side, we can quickly notice the difference. Because of recursion, we get rid of nested while loops, explicit calls to stack, and some additional conditions checking. Recursive code is more readable, clean, and concise.

Use recursion carefully

  • Recursive calls use stack implicitly, and the data structure for each call remains on the stack until the base condition is reached. So, it has a great space requirement.
  • As mentioned, every call gets stacked, so the stack size gets bigger. Therefore, the final answer is returned once the whole stack is popped, causing it to have large space complexity.

Note: It’s not always recommended to use recursion. It depends on the requirement.

RELATED TAGS

algorithms

CONTRIBUTOR

Ayyaz Sheikh
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring