Рекурсия на Python и Scala

Question

Почему эта Scala рекурсия

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

возвращается 0в то время как эта рекурсия Python возвращается None?

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

Каким образом Python и Scala обрабатывают рекурсию и управляют вложенными записями активации?

Answer 1

В Scala любой блок оценивается по значению его последнего оператора. Например, вы можете написать:

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

Вот, myVal будет оценена 9,

Точно так же ваш else блок оценивается как значение, возвращаемое из foo(id - 1) (хотя нет явного return ключевое слово), и, следовательно, значение всего тела метода будет равно этому значению, пока else блок достигнут (весь if заявление будет оцениваться в результате foo(id - 1)и с тех пор if является последним (и единственным) оператором в теле метода - это будет возвращаемое значение метода).

Вы можете бросить первый return ключевое слово:

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

В Python это просто не так; Только return операторы обозначают возвращаемое значение метода. Если вы ничего не вернете, None возвращается

Answer 2

Тебе нужно return в вашем else пункт:

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

Это с return Вы в основном присваиваете значение функции. И во-вторых, Scala выполняет оценку в последнем утверждении, в то время как Python требует return ключевое слово. Так что если foo(0) возвращает 0, foo(0) будет содержать значение 0. Так как ничего не возвращается, функция не имеет никакого значения, по умолчанию 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 здесь

Answer 3

Вам либо нужно добавить return к else пункт:

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

    return foo(id - 1)

или сделать что-то вроде:

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