Strona główna > Java > Tail recursive

Tail recursive

Zaczyna się jak kolejny wpis w stylu „java też tak może” (przykład innego tutaj).
Ostatnio doszła mnie wieść o cesze języka Scala, która to kryje się za pojęciem ‚tail recursive’. Poszukiwanie tego co to znaczy doprowadziło mnie między innymi do tego wpisu. Jest tu w miarę łopatologiczne wytłumaczenie o co chodzi w tym. Upraszczając: za tym pojęciem kryje się rodzaj pisania rekurencji w ten sposób, aby nie doprowadzić do jej wyłożenia się kiedy będzie biegła ona ku (prawie) nieskończoności.
Rekurencja nie jest mym chlebem powszednim w javie (i nie tylko)😉. Ciekawe czy jest to rodzaj wpojonego przekonania, czy z biegiem lat nabyte podskórne przekonanie, że nie tędy droga? Generalnie wiem, że w javie jest to możliwe, ale stosowanie tego w nadmiarze (nie rozważnie) może prowadzić do braku pamięci.
Wpis, do którego się tu odnoszę, podpuścił mnie do sprawdzenia czy może jedna java da radę.

Krok 1
A więc najprostsza rekurencja na przykładzie sumy wartości od 0 do zadanej liczby.

	private static int recur1(int max) {
		if (max == 0) 
			return 0;
		return max + recur1(--max);
	}

Dla nie wielkich wartości sprawdza się. Jednak dla niewinnego wywołania recur1(100000); dało oczekiwany wyjątek java.lang.StackOverflowError. No cóż java nie rozczarowała pod tym względem😉 – ma swoje ograniczenia.

Krok 2
Pokazany przykład nie jest wyrażeniem typu ‚tail recursive’ (ciekawe jak to się tłumaczy na polski?). Tak sama sytuacja była w przytaczanym wpisie: początkowe wyrażenie zostało przekształcone do typu ‚tail recursive’. Spróbowałem zrobić coś takiego samego tutaj. Nie mogłem wprowadzić anonimowej pomocniczej metody, więc użyłem klas.

	private static int recur2(final int max) {
		class Helper{
			int counter;
			int accumulator;
			public int doIt(){
				if (counter == max) 
					return accumulator;
				counter = (counter + 1);
				accumulator = accumulator + counter;
				return this.doIt();
			}
		};
		return new Helper().doIt();
	}

Jest tu parę przeskoków w stosunku do poprzedniej wersji. Pierwszy to zmiana dochodzenia do końcowego przypadku. Tutaj licznik zwiększa się, dążąc do zadanej wartości (wcześniej wartość ta była pomniejszana aż do zera). Wprowadzona klasa posiada swoje zmienne (pośrednia wersja, tego rozwiązania, obywała się bez nich ale było to tylko opakowanie wcześniejszej metody). Wszystko to aby ostatnim co było wołane w metodzie było rekurencyjne wywołanie następnej metody – co jest koniecznym warunkiem do stworzenia ‘tail recursive’.
Po utworzeniu tego monstrum: liczy się dla małych wartości poprawnie, dla wcześniejszego przypadku (recur2(100000);) wywala się tak samo😉.
No cóż architektury języka się nie przeskoczy – Scala ma tu jakąś magiczną optymalizacje, która zwija taki twór do zgrabnej postaci.
Trzeba więc pomóc językowi😉.

Krok 3
To co kompilator nie może zrobić trzeba zrobić za niego. Poniższe przykłady przechodzą już dla granicznej wartości 100000.
Na początek było spłaszczenie tego rekurencyjnego wywołania. Czyli, jak by się ktoś czepiał, jest to pozbycie się rekurencji, ale dokładnie to samo robi kompilator w przypadku Scali (tak mi się wydaję ;)). Została wprowadzona zewnętrzna pętla iterująca po zadanym zakresie i przechowująca cząstkowe wyniki.

	private static int recur3(final int max) {
		class Helper{
			int counter;
			int accumulator;
			public void doIt(){
//				if (counter == max) 
//					return accumulator;
				counter = (counter + 1);
				accumulator = accumulator + counter;
//				return doIt();
			}
		};
		Helper helper = new Helper();
		for ( ; ! (helper.counter == max) ; ) {
			helper.doIt();
		}
		return helper.accumulator;
	}

Kolejnym elementem było wyodrębnienie i nazwanie czynności, które tu występują. Ja wyróżniłem: warunek mówiący o trwaniu rekurencji; wartości zwracana na ostatnim kroku rekurencji; i czynność dokonywana w kolejnym kroku iteracji.

	private static int recur4(final int max) {
		class Helper{
			int counter;
			int accumulator;
			public void keepOn(){
				counter = (counter + 1);
				accumulator = accumulator + counter;
			}
			public boolean stopWhen(){
				return counter == max;
			}
			public int returnOnStop(){
				return accumulator;
			}
		};
		Helper helper = new Helper();
		for ( ; ! helper.stopWhen() ; ) {
			helper.keepOn();
		}
		return helper.returnOnStop();
	}

Co ostatecznie wykrystalizowało się do postaci jak poniżej:

	private static int recur5(final int max) {
		Recursion<Integer> helper = new Recursion<Integer>(){
			int counter;
			int accumulator;
			protected void keepOn(){
				counter = (counter + 1);
				accumulator = accumulator + counter;
			}
			protected boolean stopWhen(){
				return counter == max;
			}
			protected Integer returnOnStop(){
				return accumulator;
			}
		};
		return helper.doIt();
	}

	  static abstract class Recursion<T>{
			public T doIt() {
				while (!this.stopWhen()) {
					this.keepOn();
				}
				return this.returnOnStop();
			}

			protected abstract T returnOnStop();

			protected abstract void keepOn();

			protected abstract boolean stopWhen();
	  }

No i to na razie tyle, teraz może zaczynać się już specjalizacja owego ogólnego przedstawienia rekurencji, a może już nie do końca rekurencji. Jest to raczej twór, który powinien pozwalać na zastosowanie podobnej techniki co w przypadku rekurencji. Ma on zdefiniowane czynności; konkretna implementacja ogranicza się do napisania ściśle określonych w swojej roli kawałków kodu.
Przykład z implementacją silni czy innych operacji na ciągach to:

	private static long silnia(long value) {
		return new RecursionToZero(value){
			protected Long step(){
				return (counter * accumulator);
			}
		}.doIt();
	}

Gdzie brakujący element RecursionToZero wygląda tak:

	private static abstract class RecursionToZero extends Recursion<Long>{
		Long counter;
		Long accumulator;
		
		public RecursionToZero(Long counter){
			this.counter = counter;
			this.accumulator = 1L;
		}
		
		protected Long returnOnStop() {
			return accumulator;
		}

		protected void keepOn() {
			accumulator = step();
			counter = counter - 1;
		}
		
		protected abstract Long step();

		protected boolean stopWhen() {
			return counter.intValue() == 0;
		}
	}

Podsumowanie
Pójście w kierunku pokazanym w ostatnim przykładzie doprowadziło mnie trochę do kuriozalnego stwierdzenia. Całe te zabiegi, z wprowadzaniem metody szablonowej aby potem sprowadzić to do przykładu z liczeniem silni, wyglądają jak przerost formy nad treścią😉. Po co się bawić w jakąś rekurencje, wprowadzanie jakichś zabiegów aby wykonywało się bez wywalania dla wielokrotnego wywołania, jeśli ten sam przykład z silnią mogę sprowadzić do postaci zwykłej iteracji:

	private static long silnia2(long value) {
		long accumulator = 1L;
		for (long counter = value; ! (counter == 0); counter--) {
			accumulator = (counter * accumulator);
		}
		return accumulator;
	}

Cały ten post wziął się z rozważań nad rekurencją i jej implementacji w javie, a dochodzę do stwierdzenia: że rekurencja (przynajmniej przypadku ‚tail recursive’) da się zastąpić iteracją. Może to jest właśnie odpowiedz na pytania postawione na początku (dlaczego wcale tego nie używam ?).
Cóż może jakbym pisał bibliotekę do operacji na ciągach liczby to istnienie takiej struktury (Recursion) może by dawało jakiś zysk. A tak napisanie tego postu było ćwiczeniem z rekurencji i jak ona może być wyrażana w inny sposób.
PS. Całe ta tematyka też wydaje się częściowo powtórzona (choć trochę od innego strony) w poprzednim wpisie. Wygląda na to że staje się monotematyczny😉.

PS. Trafiłem na ten link, oddający chyba trochę to czym się tu zajmowałem, mam nadzieje że jak najmniej w podejściu do rozwiązania problemu😉

Kategorie:Java Tags: ,
  1. Brak komentarzy.
  1. No trackbacks yet.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d bloggers like this: