[Solved] why does the result of this recursive function in java is like that

by


Here is a test application to show you the trace of the program’s execution (requires Java 11 due to the use of String#repeat(int)):

public class Main {

  private static int depth;

  public static void main(String[] args) {
    foo(0);
  }

  public static void foo(int n) {
    printDebug("Invoked foo(" + n + ")");

    if (n < 2) {
      printDebug("Recursively call foo(" + n + " + 1)");
      depth++;
      foo(n + 1);
      depth--;
      printDebug("Returned from recursive call of foo(" + n + " + 1)");
    } else {
      printDebug("Skip recursive call");
    }


    // this is the 'System.out.print(n + " "); line'
    printDebug("PRINT VALUE OF n AND A SPACE (n=" + n + ")");

    if (n < 2) {
      printDebug("Recursively call foo(" + n + " + 1)");
      depth++;
      foo(n + 1);
      depth--;
      printDebug("Returned from recursive call of foo(" + n  + " + 1)");
    } else {
      printDebug("Skip recursive call");
    }
  }

  private static void printDebug(String msg) {
    System.out.println("    ".repeat(depth) + msg);
  }
}

The recursive function was renamed to foo and was slightly modified to accommodate debug statements. When you run the above, the output will be:

Invoked foo(0)
Recursively call foo(0 + 1)
    Invoked foo(1)
    Recursively call foo(1 + 1)
        Invoked foo(2)
        Skip recursive call
        PRINT VALUE OF n AND A SPACE (n=2)
        Skip recursive call
    Returned from recursive call of foo(1 + 1)
    PRINT VALUE OF n AND A SPACE (n=1)
    Recursively call foo(1 + 1)
        Invoked foo(2)
        Skip recursive call
        PRINT VALUE OF n AND A SPACE (n=2)
        Skip recursive call
    Returned from recursive call of foo(1 + 1)
Returned from recursive call of foo(0 + 1)
PRINT VALUE OF n AND A SPACE (n=0)
Recursively call foo(0 + 1)
    Invoked foo(1)
    Recursively call foo(1 + 1)
        Invoked foo(2)
        Skip recursive call
        PRINT VALUE OF n AND A SPACE (n=2)
        Skip recursive call
    Returned from recursive call of foo(1 + 1)
    PRINT VALUE OF n AND A SPACE (n=1)
    Recursively call foo(1 + 1)
        Invoked foo(2)
        Skip recursive call
        PRINT VALUE OF n AND A SPACE (n=2)
        Skip recursive call
    Returned from recursive call of foo(1 + 1)
Returned from recursive call of foo(0 + 1)

The indent of each line shows the current depth of the recursive calls (more indent means deeper recursion). If you look at the order of the PRINT VALUE OF n AND A SPACE (n=#) lines, you’ll see the output of the original recursive function will be:

2 1 2 0 2 1 2

solved why does the result of this recursive function in java is like that