W dniu wtorek, 19 listopada 2019 17:37:28 UTC+1 użytkownik Borneq napisał:

> > Tutaj jest Pythonowa wersja, w której umieściłem Haskellowe patterny i guardy w
komentarzach
> > return group(t, g+[h]) ### -- warunek niespelniony
> > if g:
> > return [g] ### grouped [] g -- grupa jest niepusta
> > return [] ### grouped [] [] -- pusta grupa
> > return group(l, [])
>
> To jest jakaś rekurencja ogonowa, którą można przenieść na pętlę nie
> zajmując stosu?

Nie, w tym przypadku rekurencja nie jest ogonowa, bo jedno z wywołań rekurencyjnych
jest zagnieżdżone w wywołanie innej funkcji (sklejania list).
Chodzi konkretnie o linię:

return [g+[h]]+group(t, [])

Typowo jeśli chcielibyśmy przekształcić taką rekurencję w rekurencję ogonową,
musielibyśmy stworzyć dodatkowy argument reprezentujący wynik.

Możemy tak zrobić, jeśli strukutra rekurencji jest liniowa (albo inaczej:
nie-drzewiasta). Wersja Pythonowa zapisana z rekurencją ogonową wyglądałaby tak:

def trgroups(l, cond):
def group(l, g, out):
if l:
h, *t = l
if cond(g+[h]):
return group(t, [], out+[g+[h]])
return group(t, g+[h], out)
if g:
return out+[g]
return out
return group(l, [], [])

Takie coś rzeczywiście nie powinno zajmować stosu w implementacjach optymalizujących
rekurencję ogonową (do których Pythony raczej się nie zaliczają)

Tutaj link:
https://rextester.com/FCY59693