[koziolek666]

Dziś rekurencja ogonkowa http://koziolekweb.pl/2016/06/12/rekurencja-ogonkowa-w-kotlinie/

#kotlin #koziolekweb #programowanie

[michalfranc]

@koziolek666: nigdy nie pomyslalbym ze tail call przetlumaczyc mozna na 'ogonkowy' ;d

[koziolek666]

@michalfranc: https://pl.wikipedia.org/wiki/Rekurencja_ogonowa :)

[g.....s]

@koziolek666: Co jest nie tak z fun fac(i: Int): Int {
2. if (i == 0)
3. return 1;
4. return i * fac(i - 1);
5.} ?

[michalfranc]

@g500s: nie jest to rekurencja ogonkowa, poniewaz nie mozesz zewaluowac wartosci w tym wywolaniu, tym samym na stosie wywolan funkcji to dzialanie bedzie odlozone na pozniej. Doprowadzi to do przepelnienia stosu jesli popsujesz warunek stopu.

W rekurencji ogonkowej do kolejnego wywolania funkcji przekazujesz caly stan tak ze nie musisz odkladac na stosie stanu poprzedniego.

Taka zmiana jak

return fac((i - 1) * i) powoduje ze przekazujesz cale dzialanie dalej i nie

[koziolek666]

@g500s: Chodzi o kolejność wykonania działań w linii 4. By móc zwrócić wartość muszą one zostać wykonane w kolejności:

# i-1 – zapamiętane pod adresem X
# fun(X) – zapamiętane pod Y
# i * Y – zwrócone

I teraz w drugim kroku masz skok do pierwszego. Przy odpowiednio dużej liczbie wywołań nastąpi:

# przepełnienie stosu wywołań, albo
# wyczerpanie pamięci służącej do alokowania wyników.

[g.....s]

@koziolek666: @michalfranc: dziękuję!