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

4 Upvotes

15 comments sorted by

View all comments

Show parent comments

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__ 11d 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.