Python 和 Scala 中的递归

Question

为什么这个 Scala 递归

def foo(id:Int): Int = { 
    if (id == 0) { return id } else { foo(id - 1) }
}
foo(2)

returns 0，而这个 Python 递归 returns None?

def foo(id):
    if id == 0:
        return id
    else:
        foo(id - 1)
foo(2)

Python 和 Scala 以何种方式处理递归和管理嵌套激活记录？

Answer 1

您需要在 else 子句中添加 return：

def foo(id):
    if id == 0:
        return id

    return foo(id - 1)

或者做类似的事情：

def foo(id):
    return id if id == 0 else foo(id - 1)

Answer 2

您的 else 子句中需要 return：

def foo(id):
    if id == 0:
        return id
    return foo(id - 1)

这是在 return 中，您基本上是在为函数赋值。第二，Scala 在最后一条语句中进行求值，而 Python 需要 return 关键字。因此，如果 foo(0) returns 0，则 foo(0) 将包含 0 的值。因为 nothing 是返回，函数没有任何值，默认为None.

通过使用 return，您将 foo(id-1) 的值分配给 foo(id)。但它是什么？这是递归的地方，因为要获得 foo(id-1) 的值，它必须运行函数。这种情况一遍又一遍地发生，直到你得到 0。换句话说 return:

foo(n) = foo(n-1) = foo((n-1)-1) = foo(n-2) = ... = foo(n-n) = foo(0) = 0

您可以看到 id/n here.

稳步下降

Answer 3

在 Scala 中，任何块的计算结果都是它的 最后一条语句 的值。例如，你可以这样写：

val myVal = {
  val t = 1
  val r = 8
  t + r
}

在这里，myVal 将计算为 9。

同样，您的 else 块的计算结果为从 foo(id - 1) 编辑的值 return（即使没有明确的 return 关键字），因此只要达到 else 块，整个方法主体就会计算为该值（整个 if 语句将计算为 foo(id - 1) 的结果，因为 if是方法主体中的最后（也是唯一）语句 - 这将是方法的 return 值）。

您也可以删除第一个 return 关键字：

def foo(id:Int): Int = { 
  if (id == 0) id else foo(id - 1)
}

在Python中，根本不是这样；只有 return 语句表示方法的 return 值。如果你 return 什么都没有，None 就是 returned。

Python 和 Scala 中的递归

Recursion in Python and Scala

python

recursion

scala

activation-record