OOP / języki proceduralne mają tendencję do umieszczania danych na stosie za każdym razem, gdy wykonywane jest rekurencyjne wywołanie - dlatego rekurencja nie jest tak skuteczna jak iteracja w tych językach.

Natomiast Kompilatory / interpretery dla języków funkcyjnych są zazwyczaj zaprojektowane w celu optymalizacji rekurencji ogonowej tak, aby była tak efektywna jak iteracja :

Rekurencja może wymagać utrzymania stosu, ale rekurencja ogonowa może być rozpoznana i zoptymalizowana przez kompilator do tego samego kodu, którego użyto do implementacji iteracja w językach imperatywnych. Standard języka programowania Scheme wymaga implementacji do rozpoznawania i optymalizacji rekurencji ogonowej. Optymalizacja rekurencji ogonowej może być zaimplementowana m.in. poprzez przekształcenie programu w kontynuację stylu przechodzenia podczas kompilacji.

Co to jest-tail-Call-optimization i które-języki-obsługują-tail-recursion-optimization mają bardziej szczegółowe informacje.

Jeśli używany kompilator wspiera optymalizację wywołania ogonowego i tworzysz swój kod tak, aby go wykorzystać, rekurencja nie jest nieefektywna.

Ze względu na zapobieganie rekursji w programowaniu funkcyjnym, Kompilatory języków funkcyjnych są bardziej prawdopodobne, aby wdrożyć optymalizację wywołań ogonowych niż proceduralnych.

Efektywna rekurencja w XSLT

Istnieją dwa główne sposoby osiągnięcia efektywnej rekurencji w XSLT:

1. Optymalizacja rekurencji ogonowej
2. Divide and Conquer (DVC)

Istnieje wiele odpowiedzi dotyczących rekurencji ogonowej, więc oto prosty przykład:

  <xsl:function name="my:sum">
   <xsl:param name="pAccum" as="xs:double*"/>
   <xsl:param name="pNums" as="xs:double*"/>

   <xsl:sequence select=
     "if(empty($pNums))
        then $pAccum
        else
           my:sum($pAccum + $pNums[1], $pNums[position() >1])
     "
   />
 </xsl:function>

Można sprawdzić, czy my:sum(0, 1 do 100) jest oceniane na: 5050.

Oto jak można zaimplementować funkcję sum() w DVC sposób :

  <xsl:function name="my:sum2">
      <xsl:param name="pNums" as="xs:double*"/>

      <xsl:sequence select=
        "if(empty($pNums))
          then 0
          else
            if(count($pNums) eq 1)
              then $pNums[1]
              else
                for $half in count($pNums) idiv 2
                  return
                    my:sum2($pNums[not(position() gt $half)]) 
                   + 
                    my:sum2($pNums[position() gt $half])

        "
      />
  </xsl:function>

Główną ideą DVC jest podzielenie sekwencji wejściowej na dwie (zazwyczaj) lub więcej części i przetwarzanie ich niezależnie od siebie, a następnie połączenie wyników w celu uzyskania wyniku dla całkowitej sekwencji wejściowej.

Należy zauważyć, że dla sekwencji N elementów maksymalna głębokość stosu wywołań w dowolnym momencie nie przekroczy log2(N), co jest więcej niż wystarczające dla najbardziej praktycznych celów. Na przykład maksymalna głębokość stosu wywołań przy przetwarzaniu sekwencji 1000000 (1M) elementów wynosiłaby tylko 19.

Chociaż istnieją procesory XSLT, które nie są wystarczająco inteligentne, aby rozpoznawać i optymalizować rekurencję ogonową, szablon DVC-recursive działa na każdym procesorze XSLT.

Jedyne, co muszę dodać do odpowiedzi, to to, że wiele języków jest zakładnikami legacy calling conventions. Nigdzie nie jest to bardziej prawdziwe niż języki, które są zgodne z konwencją wywołującą C na x86: każdy parametr trafia na stos. Języki funkcyjne przekazują co najmniej niektóre parametry w rejestrach, i tak na platformach 32-bitowych, nawet wywołania bez ogona (których nie można zoptymalizować) są nadal bardziej wydajne niż, powiedzmy, C.

Dzięki Bogu x86-64 ma przyzwoitą konwencję C!

Jeśli język nie jest zoptymalizowany przez kompilator, rekurencja prawdopodobnie będzie wolniejsza niż iteracja, ponieważ na początku schodzenia w dół danego pasa, Co jest prawie równoznaczne z iteracją, musisz prześledzić swoje kroki z powrotem na górę po zakończeniu zadania.

W Przeciwnym Razie jest to prawie równoważne, z wyjątkiem tego, że może być znacznie bardziej eleganckie, ponieważ pozwalasz kompilatorowi i systemowi zająć się pętlą za kulisami. I oczywiście są zadania (np. przetwarzanie drzewopodobnych struktur) gdzie rekurencja jest jedynym sposobem (a przynajmniej jedynym, który nie jest beznadziejnie zawiły).

To, co sprawia, że rekurencja jest szybka w językach funkcyjnych, to fakt, że Kompilatory mogą wewnętrznie przekształcić rekurencję w iterację za pomocą eliminacji rekurencji ogonowej (lub ogólniej, eliminacji wywołań ogonowych). Zasadniczo, jeśli rekurencyjne wywołanie jest ostatnią operacją przed powrotem funkcji, a wartością zwracaną funkcji jest wartość wywołania rekurencyjnego, to zamiast tworzyć nową ramkę stosu, program użyje ponownie bieżącej ramki. Zmienne argumentu są ustawione na nowe wartości, a komputer jest ustawiony na początek funkcji.

Wykorzystanie eliminacji rekurencji ogonowej wymaga pewnej świadomości programisty. Musisz się upewnić, że Twoje rekurencyjne wywołania są rzeczywiście wywołaniami ogonowymi. Na przykład, oto kod w OCaml do obliczenia czynnika:

let rec factorial n =
  if n = 0 then
    1
  else
    n * factorial (n - 1)

Eliminacja wywołania ogonowego nie działałaby tutaj bezpośrednio, ponieważ mnożenie musi być wykonywane po wywołaniu rekurencyjnym. Jeśli jednak funkcja została przepisana w ten sposób:

let factorial n =
  let rec fac_helper n p =
    if n = 0 then
      p
    else
      fac_helper (n - 1) (p * n)
   in
   fac_helper n 1

Teraz eliminacja wywołania ogonowego może być używany. To zostałoby przekształcone na coś takiego (w pseudokodzie):

factorial p n = 
  p = 1
  while n > 0
    n = n - 1
    p = p * n
  return p

Ten styl może wydawać się sprzeczny z intuicją, ale ma taki sam sens jak wersja iteracyjna. Każdy etap obliczeń jest wykonywany w wywołaniu funkcji rekurencyjnej. Zmienne indukcyjne, takie jak p i n powyżej, które są używane w całym obliczeniu, są deklarowane jako argumenty.

Należy zauważyć, że większość kompilatorów zarówno dla języków imperatywnych, jak i funkcyjnych korzysta z ta optymalizacja. W rzeczywistości wersja optymalizacji LLVM pozwala nawet na operacje asocjacyjne między wywołaniem rekurencyjnym a zwrotem, więc możesz napisać pierwszą wersję factorial i nadal korzystać z optymalizacji. Jednak eliminacja wywołań ogonowych nie jest obsługiwana w JVM, więc języki funkcjonalne w JVM, takie jak Scala, mają tylko ograniczone wsparcie dla niego.

Nie zakładaj, że rekurencja a iteracja to miejsce, w którym powinieneś się martwić.

Zazwyczaj staje się to istotne po wyeliminowaniu serii większych problemów z wydajnością .