Почему этот хвост рекурсивный? - PullRequest
Новая
       4

Почему этот хвост рекурсивный?

7 голосов
/ 17 марта 2011

проверить этот Scala-код: 

def rec(n: Int) {
  if (n > 1) {
    val d = n / 2
    rec(d)
//    if (d > 1)  // abort loop
      rec(n/d)
  }
}

Этот код приведет к бесконечному циклу. Из-за хвостовой рекурсивной оптимизации я не получаю StackOverflowError.

Декомпилировано с JAD Я получил этот Java-код: 

public void rec(int n)
{
    int d;
    for(; n > 1; n /= d)
    {
        int i = n;
        d = i / 2;
        rec(d);
    }
}

В последней строке цикла метод вызывает сам себя, поэтому я не понимаю позицию хвостового вызова. Кто-нибудь, кто может объяснить это?

Ответы [ 2 ]

9 голосов
/ 17 марта 2011

В случае rec(d) хвостовой вызов отсутствует. Для rec(N) (где N > 1) стек больше не увеличивается после log2(N) вызовов (потому что после этого n всегда равен 2 или 3, а d равно 1). После этого это просто бесконечный цикл с внутренним вызовом rec(1), который немедленно возвращается каждый раз. Вот почему нет переполнения стека.

3 голосов
/ 17 марта 2011

В рекурсивной форме вашего метода у вас есть два рекурсивных вызова. StackOverflowError вызвано последним из них.

Из-за оптимизации хвостовой рекурсии последний вызов превращается в цикл (тогда как первый вызов остается рекурсивным), поэтому вместо бесконечной рекурсии у вас бесконечный цикл, и StackOverflowError не происходит.

...