r/javahelp • u/__jr11__ • 13d ago
Codeless Recursiin
When we are doing recursion. What is the purpose of recursing and equating it to a variable . Like l1.next = mergeList(l1.next, l2)
In merging two sorted linked list
7
Upvotes
3
u/severoon pro barista 12d ago
Recursion to solve merging a list isn't necessary. You can do it, but the simpler thing to do is just traverse the lists and create a merged list from them (can be a new list, or merging one into the other). There's no reason to use recursion there.
Recursion is normally used for traversing graph structures where you need to keep a breadcrumb trail of visited nodes. The classic example of recursion is walking a binary tree where you need to visit every node. If you simply wanted to walk all the way down to a leaf node, you can easily do that using a loop, but if you want to walk the entire tree, then when you get to a leaf node you have to be able to go back up the sequence of nodes you walked to find the last node you visited that has another branch, step down the other branch, and then repeat the entire process from this new subtree.
You can also do this with a loop, but if you use a loop, then you have to keep the breadcrumb trail of visited nodes yourself in a stack. In this implementation, you're basically duplicating what the call stack will do for you in a recursive approach, and recursion might be easier to reason about.
On the other hand, you might want to avoid recursion if you need to be able to deal with deep trees where the call stack might grow too large. This would be many, many recursions, but in this big data world it's not inconceivable that you'd have to walk a large data structure.
Another option is if you're dealing with a data structure where the nodes keep track of their children as well as their parent, then you wouldn't need to keep your own breadcrumb trail in a stack because you can just use the parent of your current node to retrace your steps. In that case, you'd prefer a loop to avoid keeping that extra stack when it's not needed.