java - 无法理解 java 回文输出

Question

我有一个简单的 java 程序，它接受一个数字并根据该数字执行一个函数。

public class Palidrome {
public static void main (String[] args) {
    int N = 3;
    System.out.println(palidrome(N));
}

public static String palidrome(int i) {
    if (i == 0) return "S";
    if (i == 1) return "T";
    return palidrome(i-2) 
            + palidrome(i-1)
            + palidrome(i-2);
    }
}

所以对于这个例子 N = 3，输出是“TSTST”。如果将 N 更改为 5，则输出为“TSTSTSTSTSTSTSTSTSTSTST”等。

我正在努力弄清楚为什么会这样。如果 N = 5，palidrome(i-1) 和 palidrome(i-2) 将永远不会到达 (i == 0) 或 (i == 1)，所以理论上什么都不应该返回？

提前致谢!

Answer 1

这个可以通过画递归树来理解。

                                            palindrome(5)
                                         /        |         \   
                            palindrome(3)     palindrome(4)  palindrome(3)
                           /     |        \  ............................
                          /      |         \
              palindrome(1)   palindrome(2)  palindrome(1)
                             /     |       \
                            /      |        \
              palindrome(0)  palindrome(1)  palindrome(0)

因此 palindrome(5) 最终会到达 palindrome(0) 和 palindrome(1) 调用。
注意:递归在 palindrome(0) 和 palindrome(1) 调用结束。