递归 - 它做了什么

Question

我的智慧结束了...我理解递归的更简单的例子,但是当它变得棘手时我没有线索.这是一个例子.如果有人能说出它的作用,我会很高兴的.编译器做了什么......

public static char mystery(String s, int n, int m)
{
if (n==1) return s.charAt(m);

char first = mystery(s, n/2, m*2);
char second = mystery(s, n/2, m*2 +1);

System.out.print(first + " " + second + " ");

return first; 
}

调用方法时打印的内容:mystery("fredpass",5,1)

答案是传递

我没有CLUE如何到达那里......

如果有人可以帮我解决这个问题,真的会很感激.在互联网上的其他地方,他们只解释了阶乘 - 简单的例子.不确定如果你char first = mystery ( blah );再次调用它两次会发生什么char second = mystery ( blah );

Answer 1

因此,您已经知道了递归的示例以及如何使用它.

也许您所缺少的是递归的原因.为了理解这一点,您需要知道调用方法时会发生什么.熟悉调用堆栈.

就逻辑上发生的事情而言,您应该只考虑按顺序"遍历"代码.当您以递归方式调用方法时,它将返回结果并继续执行,就像在任何其他过程代码中一样.但是,每个方法调用都有自己的变量范围,这些变量仅在递归的特定调用中有效.

Answer 2

只需手动追踪电话:

mystery(5, 1)
    first = mystery(2, 2)
        first = mystery(1, 4) = 'p'
        second = mystery(1, 5) = 'a'
    second = mystery(2, 3)
        ...

等等.给自己足够的纸张来绘制调用堆栈的完整画面,函数调用的状态和局部变量.例如,在我的图片中最里面的调用打印"pa"后,它返回'p',所以我会在之后写这封信mystery(2, 2).