7.18. Rekurencja ogonowa

Metody definiowane w języku Scala mogą odwoływać się do samych siebie, czyli wywoływać się rekurencyjnie. W pliku Tail1.scala zdefiniowany jest obiekt Loops, w którym zdefiniowane są dwie rekurencyjne metody. Każda z tych metod służy do powtarzalnego wykonywania jakiegoś kodu. Pierwszy parametr metody określa liczbę powtórzeń, a drugi reprezentuje powtarzany kod.

Plik Tail1.scala:
object Loops {
  def repeat1(n: Int, body: => Unit) {
    if (n > 1) repeat1(n-1, body) 
    body 
  }
  def repeat2(n: Int, body: => Unit) {
    body
    if (n > 1) repeat2(n-1, body) 
  }
}

Metoda repeat1 najpierw sprawdza warunek powtarzania, a potem wykonuje blok kodu, a metoda repeat2 na odwrót. Każda z metod wykonuje blok kodu przynajmniej raz, niezależnie od wartości pierwszego parametru.

scala> Loops.repeat1(4, println("hello"))
hello
hello
hello
hello

scala> Loops.repeat2(4, println("hello"))
hello
hello
hello
hello

scala> Loops.repeat1(0, println("hello"))
hello

scala> Loops.repeat2(0, println("hello"))
hello

Między oboma metodami istnieje różnica, na którą warto zwrócić uwagę. W metodzie repeat1 rekurencyjne wywołanie metody nie jest ostatnią operacją wykonywaną w tej metodzie. Po powrocie z rekurencyjnego wywołania (wiersz ) pozostaje jeszcze do wykonania wyrażenie reprezentowane przez parametr body (wiersz ). Konsekwencją tego jest alokowanie kolejnych ramek pamięci w czasie wykonania programu. W przypadku, gdy liczba powtórzeń pętli będzie duża, może zostać wygenerowany wyjątek. W przykładzie z wiersza rzeczywiście tak się dzieje.

scala> Loops.repeat1(100, ())

scala> Loops.repeat1(100000, ()) 
java.lang.StackOverflowError
  at Loops$.repeat1(Tail1.scala:3)
  at Loops$.repeat1(Tail1.scala:3)
…

Wywołanie metody z parametrem n równym 100 nie spowodowało wystąpienia wyjątku. Natomiast wywołanie metody z n równym 100000 zakończyło się błędem przekroczenia rozmiaru stosu. Kolejne zagnieżdżone wywołania metody skutkowały alokowaniem coraz to nowych ramek, aż do wyczerpania dostępnej pamięci stosu.

Metoda repeat2 jest zaimplementowana inaczej. W tej metodzie rekurencyjne wywołanie jest ostatnią wykonywaną operacją. Po powrocie z rekurencyjnego wywołania (wiersz ) nie ma już w tej metodzie nic do zrobienia. Mówimy, że rekurencyjne wywołanie metody występuje w pozycji ogonowej. Kompilator języka Scala generuje kod metody repeat2 w taki sposób, żeby nie alokować nowej ramki dla każdego rekurencyjnego wywołania. Nowa ramka nie jest potrzebna, gdyż po powrocie z rekurencyjnego wywołania metody nie ma już nic więcej do zrobienia, a więc nie trzeba pamiętać na stosie żadnych informacji, które mogłyby być potrzebne w razie kontynuacji wykonywania metody. Dzięki temu metodę repeat2 można wywołać nawet z dużą liczbą powtórzeń, która w przypadku metody repeat1 powoduje wygenerowanie wyjątku.

scala> Loops.repeat2(1000, ())

scala> Loops.repeat2(100000, ())

scala> Loops.repeat2(100000000, ())

scala> 

Różnicę w działaniu metod repeat1 i repeat2 można zilustrować w następujący sposób. W poniższych wywołaniach tych metod wyrażenie, którego wywołanie jest powtarzane, wyświetla długość zrzutu stosu wyjątku.

scala> Loops.repeat1(5, println((new Throwable).getStackTrace.length)) 
39
38
37
36
35

scala> Loops.repeat2(5, println((new Throwable).getStackTrace.length)) 
35
35
35
35
35

W przypadku użycia metody repeat1 (wiersz ) długość zrzutu stosu zmienia się w kolejnych iteracjach, natomiast w przypadku metody repeat2 (wiersz ) nie zmienia się.

Optymalizacja wywołań rekurencyjnych nie zostanie zastosowana, jeśli metoda może potencjalnie zostać nadpisana w klasie podrzędnej. W przypadku kodu z pliku Tail1.scala nadpisanie metody repeat2 jest niemożliwe, gdyż została zdefiniowana w obiekcie. Inaczej jest w przypadku metody repeat2 z pliku Tail2.scala, która jest zaimplementowana w klasie Loops2 i potencjalnie mogłaby zostać nadpisana w klasie potomnej.

Plik Tail2.scala:
class Loops2 {
  def repeat2(n: Int, body: => Unit) {
    body
    if (n > 1) repeat2(n-1, body)
  }
}

Poniższe wywołanie metody repeat2 z klasy Loops pokazuje, że optymalizacja wywołań nie została zastosowana.

scala> (new Loops2).repeat2(5, println((new Throwable).getStackTrace.length))
35
36
37
38
39