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

посмотрите этот 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);
    }
}

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


scala tail-recursion
person kiritsuku    schedule 17.03.2011    source источник
comment
Это будет полезно 1. cs. wayne.edu/~artem/main/teaching/csc3200ss2006/slides/ 2. stackoverflow.com/questions/105834/   -  person Dead Programmer    schedule 17.03.2011

Ответы (2)


arrow_upward
9
arrow_downward

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

person hoha    schedule 17.03.2011

arrow_upward
3
arrow_downward

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

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

person axtavt    schedule 17.03.2011