I'm having a hard time trying to understand why this code works

so we have a tree which we use this method to calculate the height

the problem for me is how does this method work to calculate the total height of the tree without a loop or something like that from my own understanding this can only work for 1 node but i cant see how is it possible to work for the whole tree without any kind of iteration

public int height() {
    if (isEmpty()) {
        return -1;
    }
    else {
        int leftHeight = left.height();
        int rightHeight = right.height();
        return Math.max(leftHeight, rightHeight) 1;
    }
}

CodePudding user response：

But recursion is a kind of iteration.

A conventional loop repeats a computational recipe, a loop's body, with (potentially) new values of the loop variables on each repetition, until the stopping condition is met.

A recursive function repeats a computational recipe, a function's body, with (potentially) new values of its parameter variables on each invocation, until the base test condition is met -- then, the preceding invocations are returned to, and continue executing their computational recipe(s) -- which is the same recipe, since it's the same function -- until all computations are finished.

Conceptually, it's the same thing.

Specifically, your example invokes the same recipe -- the function for calculating the height of a binary tree -- separately for each of the argument tree's branches, which are themselves trees as well, just like the argument tree itself. Just like a loop's body is the same for all the iterations.

So your function calculates the height of the left branch, saves it in a temporary variable; calculates the height of the right branch, saves it in another temporary variable; and then combines the two results to produce its own result.

Thus it repeats a lot of computational steps over and over.

When a particular invocation encounters a leaf, this is treated as a base case. This invocation then just returns its result directly, without invoking any more instances of the same recipe.

As an illustration, (writing height <tree> to mean <tree>.height()),

height { {{* 1 *} 2 *} 3 {* 4 {{* 5 *} 6 *}} }
=
 set
  a = height {{* 1 *} 2 *}
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = height {* 1 *}
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = /// height {* 1 *}
                   set a3 = height *
                       b3 = height *
                       return max(a3,b3) 1
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = /// height {* 1 *}
                   set a3 = -1
                       b3 = height *
                       return max(a3,b3) 1
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = /// height {* 1 *}
                   set a3 = -1
                       b3 = -1
                       return max(a3,b3) 1
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = /// height {* 1 *}
                       return max(-1,-1) 1
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = 0
            b2 = height *
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
        set a2 = 0
            b2 = -1
            return max(a2,b2) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = /// height {{* 1 *} 2 *}
            return max(0,-1) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=

continuing,

=
 set
  a = /// height {{* 1 *} 2 *}
            return max(0,-1) 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = 1
  b = height {* 4 {{* 5 *} 6 *}}
  return max(a,b) 1
=
 set
  a = 1
  b = /// height {* 4 {{* 5 *} 6 *}}
        set a2 = height *
            b2 = height {{* 5 *} 6 *}
            return max(a2,b2) 1
  return max(a,b) 1
=
...... etc.

Just as outer variables' values are remembered between each invocation of a loop's body, the variables belonging to outer invocation of a recursive function are remembered while the inner invocations do their work.

The key here is that each invocation of a recursive function is a copy of the same computational recipe, together with its own set of variables whose use is prescribed by that recipe.

So the recipe is the same, but each copy is separate, independent, different. A given copy (i.e. invocation) works with its own set of the function recipe's variables, and remembers by which copy it was invoked -- so that's where its result will be returned to, when this copy finishes its work.

And when the topmost copy -- the very first to be invoked -- finishes up, the whole work is done, and the final result is returned as the overall value.