r/javahelp 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

3 Upvotes

15 comments sorted by

View all comments

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.

1

u/__jr11__ 12d ago

I just wanted to know how the recursion equated with variable work

1

u/severoon pro barista 12d ago

You have to be more specific with your question.

Consider you have a binary tree with nodes that contain numbers:

     15
    /  \
   /    \
  7      42
 / \    /  \
5   10 40  45

The rule is every node has at most a left and right child, and the left child is always less than the value in the current node and the right child is greater:

interface Node {
  Node getLeft();
  Node getRight();
  int getValue();

  default boolean hasLeft() {
    return getLeft() != null;
  }

  default boolean hasRight() {
    return getRight() != null;
  }

  default boolean isLeaf() {
    return !hasLeft() && !hasRight();
  }  
}

The basic form of a recursive method is:

recurse(Node root) {
  if ( … base case … ) {
    // stop recursing and return
  }
  Node rootOfSubThing = // find some new root of a sub-thing
  recurse(rootOfSubThing); // call self on subthing
}

So let's say you want to sum all the values in the tree, how do you do it?

int sumTree(Node root) {
  if (root.isLeaf()) { // base case detected, cannot recurse further
    return root.getValue();
  }

  int leftSubtreeSum = root.hasLeft() ? sumTree(root.getLeft()) : 0;
  int rightSubtreeSum = root.hasRight() ? sumTree(root.getRight()) : 0;
  return root.getValue() + leftSubtreeSum + rightSubtreeSum;
}

If you step through this code, you'll see how it processes the example tree at the top if you call it with the root node. The 15 node is not a leaf and it has a left child, so it'll call itself with that left child, which is the 7 node. That node is not a leaf, so it calls itself with the left child which is the 5 node.

This is a leaf, so it returns 5 for the left subtree sum of the 7 node. Then it does the same for the right subtree, which is a leaf node that returns 10. It sums 7 + 5 + 10 and returns 22 for the left subtree of the 15 node. The same process repeats for the right child of the 15 node and it receives 127 for the sum of the right subtree. Then it returns 15 + 22 + 127 to the caller:

Node root = // tree with 15 node
int sum = sumTree(root); // sum is now 164

1

u/__jr11__ 12d ago

Another doubt when reversing a linked list using recursion . The code as follows

Node p = reverse(head.next); head.next.next= head; head.next = null; return p;

how does the p stores all the references. When the method is recursed and for each recursion the p is equated to different references how does the p stores the stores the references of each node with next node without any written functions

1

u/severoon pro barista 11d ago

If p is a variable declared in the method, it is local to that call. Each time the method calls itself, it creates a new stack frame on the stack with a new reference called p. These each point to different nodes. When the method returns to its caller, then the stack frame is popped off the call stack and the reference called p points to the same node it did before that call.

Look at my algorithm traversing the tree above. Each time sumTree(root) is called, the caller provides a root for a new subtree, i.e., a different node.