Запутанная последовательность вызовов в scala рекурсии - PullRequest
Новая
       20

Запутанная последовательность вызовов в scala рекурсии

1 голос
/ 17 апреля 2020

Я пытаюсь отследить обработку рекурсии в scala. Ниже приведен пример кода: 

def factorial(n: Int): Int =
  if (n <= 1) 1
  else {
    println("Computing factorial of " + n + " - I first need factorial of " + (n-1))
    def result = n * factorial(n - 1)
    println("Computed factorial of " + n)
    result
  }
println(factorial(3))

Ниже приводится вывод: 

Computing factorial of 3 - I first need factorial of 2
Computed factorial of 3
Computing factorial of 2 - I first need factorial of 1
Computed factorial of 2
6

И это довольно странно, поскольку параметр n нельзя вычислить до параметра n-1. Я предпочел бы ожидать следующий вывод: 

Computing factorial of 3 - I first need factorial of 2
Computing factorial of 2 - I first need factorial of 1
Computed factorial of 2
Computed factorial of 3
6

В чем причина такого поведения?

Ответы [ 2 ]

7 голосов
/ 17 апреля 2020

Ожидаемое поведение будет для следующей программы: 

def factorial(n: Int): Int =
  if (n <= 1) 1
  else {
    println("Computing factorial of " + n + " - I first need factorial of " + (n-1))
    val result = n * factorial(n - 1) // here is the difference def -> val
    println("Computed factorial of " + n)
    result
  }
println(factorial(3))

Между отпечатками вы определяете функцию: 

def result = n * factorial(n - 1)

, но это не значит, что вы вызываете Это. Функция (def) оценивается лениво, а значение (val) - охотно. Это только определение. После этого вы переходите ко второму println и result, где возвращается значение, вызывается функция result, которая выдает операторы печати для n - 1.

0 голосов
/ 17 апреля 2020

Рекурсия это круто, хвостовая рекурсия лучше. 

def factorial(n: Long): Long = {
  @annotation.tailrec
  def go(fact: Long, n: Long): Long = {
    if (n < 2) fact * n
    else go(fact * n, n - 1)
  }
  if (n == 0) 1 else go(1, n)
}
...