在递归函数中,一系列返回如何组合回单个结果？

Question

我试图了解这个递归函数中发生了什么.它反转了一个String,但我不太明白这些单独的返回调用最后是如何组合成一个字符串的.

def reverse(string: String): String = {
    if (string.length() == 0)
      return string
    return reverse(string.substring(1)) + string.charAt(0)
  }

我已经通过添加print语句分析了这个功能,虽然我有点理解它是如何工作的(概念上),我不明白,嗯...... 它是如何工作的.

例如,我知道递归的每个循环都将事物推入堆栈.

所以,我希望reverse("hello"),成为一堆

o
l
l
e
h

但它必须比那更复杂,因为递归调用是return reverse(string.substring(1)) + string.charAt(0).实际上堆栈也是如此

o, 
l, o
l, lo
e, llo
H, ello  

？

如何将它变成我们期望的单个字符串？

Answer 1

堆栈包含所有局部变量,以及递归出现的表达式中的任何临时结果(尽管那些被推送到堆栈上,即使没有递归,因为JVM是一个堆栈机器),当然,代码执行的点应该在返回时恢复.

在这种情况下,递归调用是整个表达式(也就是说,reverse在它出现的表达式之前没有计算任何内容).所以除了代码指针之外唯一的东西是string.在最深层次的递归中,堆栈将如下所示:

level    string
5        (empty string)
4        o
3        lo
2        llo
1        ello
0        hello

因此,当对级别5的调用返回时,级别4将完成计算作为reverse其一部分的表达式reverse(string.substring(1)) + string.charAt(0).的值reverse(string.substring(1))是空字符串,和的值string.charAt(0)就是o(因为的值string在第4层是o).结果是o,返回.

在第3级,它加到从第4级(返回值o)与string.charAt(0)供string等于lo,这是l,造成ol.

在2级,它加到ol用l,给人oll.

1级符连接oll带e,返回olle.

0级,最后,串接olle有h,返回olleh给调用者.

最后一点,当进行调用时,推入堆栈的内容是代码和参数的返回点.hello参数to reverse也是如此,它被reverse调用者推入堆栈.

Answer 2

使用替换模型来解决问题:

reverse("hello") =
(reverse("ello") + 'h') =
((reverse("llo") + 'e') + 'h') =
(((reverse("lo") + 'l') + 'e') + 'h') =
((((reverse("o") + 'l') + 'l') + 'e') + 'h') =
(((((reverse("") + 'o') + 'l') + 'l') + 'e') + 'h') =
((((("" + 'o') + 'l') + 'l') + 'e') + 'h') =
(((("o" + 'l') + 'l') + 'e') + 'h') =
((("ol" + 'l') + 'e') + 'h') =
(("oll" + 'e') + 'h') =
("olle" + 'h') =
"olleh"