Recursion is a method where a function calls itself to solve a problem by dividing it into smaller subproblems.
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
/* 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 nodeof the tree */while (currentNode != NULL){nodeStack.push(currentNode);currentNode = currentNode->left;}/* After traversing the left subtree, currentNodemust be NULL at this point */currentNode = nodeStack.top();nodeStack.pop();cout << currentNode->data << " ";/* Till this point, we have visited the nodeand 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
currentNodeofNodetype and point to theroot. -
Lines 7 to 28: We define a
whileloop that checks two conditions with||. This loop keeps executing until either of the conditions remainstrue. -
Lines 11–15: We define another
whileloop, which checks thecurrentNodeand keeps executing until it becomesNULL. Inside this loop, line 13 pushes thecurrentNodeonto the stack, and line 14 moves thecurrentNodepointer to its left node. Thiswhileloop traverses the left subtree and terminates the execution whencurrentNodebecomesNULL. -
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
dataof thecurrentNodeto 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 abinary 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
inOrderis declared, taking a pointer to aNodeas 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
nodeisNULL, 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:
High space complexity: Each recursive call uses stack memory until the base condition is met.
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?
Why is recursion better than iteration in some cases?
When should recursion be avoided?
How does recursion affect space complexity?
Free Resources
Copyright ©2024 Educative, Inc. All rights reserved
TRENDING TOPICS
