How java creates and passes parameters when dealing with the recursion？

Question

Take the problem of finding the maximum depth of a binary tree as an example. (A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.)

The following code is part of the codes. With each recursive call, the value of depth is modified by depth++ of the function at the previous level, but when the function ends and returns to the function at the previous level, there is no need to perform a depth-- and even a depth+=100 could run perfectly.

IntelliJ will prompt that "the value changed at depth += 100 will never be used". This line will be executed neverthless, yet the the changing is in vain.

So what happened in the JVM? How many times has the variable depth actually been created in the stack memory? Is a new int depth created every time the function is called? Or do all functions have variables that point to the same int depth? If the former, then I think depth-- should be necessary, and if the latter, then I think each time you go to the next level of recursion, the depth passed in can only be 0. So now I am confused.

This is my first question in stackoverflow, and my English is not as good as a native speaker. I Hope my description is clear enough. Thanks to anyone who cares about this question, and I appreciate your help!

   public static void max(TreeNode root,int depth){
        if(root == null) return;
        depth ++
        max(root.left,depth);
        max(root.right,depth);
        depth += 100;
    }

"Is a new int depth created every time the function is called?" Yes, why do you think this makes `depth--;` necessary? It is precisely because each method (stack frame) having its own `depth` variable that makes `depth--;` *unnecessary*. — Sweeper, Mar 10 '23 at 00:53
Oh, because I thought I need a `depth--` at the postorder position when it meets an empty node and returns to the previous node. However, why `depth` could not be modified successfully here, I mean, if the code is : max(root.left,depth); max(root.right,depth); depth ++; then it will not work. — B_flee, Mar 10 '23 at 01:13
See "call by value": https://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_value — boneill, Mar 10 '23 at 01:52
Part of what might be confusing you is that this implementation is incorrect. For one thing, it should return the `depth`. It also needs to compare the values returned for the left and right sub-trees to see which is deeper. — Tim Moore, Mar 10 '23 at 02:01

trincot · Accepted Answer · 2023-03-10T07:33:04.627

First of all, the code does not do what is described. The initial caller will not get the depth of the tree. The function will have done all this work for nothing.

As to your remarks and questions:

IntelliJ will prompt that "the value changed at depth += 100 will never be used".

This is true, because right after that statement, the function's execution context is destroyed and the variable depth ceases to exist -- the memory used for it is disposed.

How many times has the variable depth actually been created in the stack memory? Is a new int depth created every time the function is called?

Yes, a new int depth is created every time the function is called. It is a variable that is local to the function's execution context: it is created when the function starts executing, is initialised by assigning a value that is provided by the caller, and is destroyed when the function returns.

...then I think depth-- should be necessary.

No. At the end of the function's execution, the depth variable will cease to exist, so making a "last-minute" assignment to it serves no purpose at all. No-one is looking at that variable except the current execution context, which is about to end.

Be aware that the caller's depth variable has nothing to do with the callee's depth variable. An assignment to the latter (like with =, += or ++) has no influence on the first. The caller's depth variable will not (and cannot) be assigned a new value by passing it as argument to a function call.

The solution is to have the function return the depth:

   public static int max(TreeNode root) { // No depth parameter!
        if(root == null) return 0;
        // Get the depths returned by recursive calls and derive a
        //    new depth-value from those, and return that to caller
        return 1 + Math.max(max(root.left), max(root.right));
   }

Very helpful! So sad I am still a new StackOverflow user who needs more reputation to upvote your answer. I will do so once I am qualified. Thank you! — B_flee, Mar 10 '23 at 18:58

How java creates and passes parameters when dealing with the recursion？

1 Answers1