Scala递归，溢出

Question

这里有 2 个函数：

def Foo1(s: ((BigInt, Long) => Long)
=> ((BigInt, Long) => Long)): (BigInt, Long) => Long = s(Foo1(s))

def Foo2(s: (=> (BigInt, Long) => Long)
=> ((BigInt, Long) => Long)): (BigInt, Long) => Long = s(Foo2(s))

当使用以下参数调用它们时：

Foo1(rec => (x, s) =>
          if (x == 1) s
          else rec(if (x % 2 == 0) x / 2 else 3 * x + 1, s + 1))(56, 0)    
Foo2(rec => (x, s) =>
          if (x == 1) s
          else rec(if (x % 2 == 0) x / 2 else 3 * x + 1, s + 1))(56, 0)

第一个导致栈溢出，第二个正常执行。

另外，这个表达式是什么意思：(=> (BigInt, Long) => Long)?

Answer 1

签名(=> (BigInt, Long) => Long)表示一个按名称调用的参数，是理解为什么Foo2不会溢出堆栈的关键。

在 Scala 中理解函数的方法是将参数替换到函数的定义中。然后在评估参数时重复替换。我们还必须认识到 s 在两个不同的地方使用，一个作为 Foo 函数的参数，一个作为传递给 Foo.[= 的未命名函数中的参数。 27=]

评估第一个函数调用将参数 s 绑定到

rec => (x, s) => if (x == 1) s else rec(if (x % 2 == 0) x / 2 else 3 * x + 1, s + 1)

将 rec 转换为两个参数的递归函数，一个 BigInt 和一个 Long.

然后计算Foo1，将s的表达式值，外层的，代入s( Foo1( s ) )。这产生：

( rec => (x, s) =>
          if (x == 1) s
          else rec(if (x % 2 == 0) x / 2 else 3 * x + 1, s + 1) ) ( Foo1( rec => (x, s) =>
          if (x == 1) s
          else rec(if (x % 2 == 0) x / 2 else 3 * x + 1, s + 1) )

然后您需要计算 Foo1，将函数传递给它。这将递归进行，直到您运行出栈 space。

Foo2，另一方面，使用按名称调用语法而不是按值调用，因此它不需要进行第二阶段的评估，直到参数 (56, 0)，实际上是绑定的。

Scala递归，溢出

Scala recursion, overflow

stack-overflow

recursion

scala