la récursivité tail vs avant la récursivité

Une queue fonction récursive est une fonction où le seul appel récursif est la dernière dans la fonction. Un non-queue fonction récursive est une fonction qui n'est pas le cas.

Une descendante de la récursivité est une récursivité dans chaque appel récursif de la valeur du paramètre est inférieure à celle dans l'étape précédente. Avant la récursivité est une récursivité où il grandit avec chaque étape.

Ceux sont deux concepts orthogonaux, c'est à dire avant la récursivité peut ou peut ne pas être récursives terminales et la même chose s'applique à l'arrière récurrences.

Par exemple de la fonction factorielle est souvent écrit dans des langages impératifs:

fac = 1
for i from 1 to n:
    fac := fac * i

La commune une version récursive de la factorielle compte à rebours (c'est à dire qu'il appelle lui-même avec n-1 en tant que paramètre), cependant, si vous souhaitez traduire directement les ci-dessus impératif solution, il vous serait venu avec une version récursive qui compte vers le haut. Il ressemblerait à quelque chose comme ceci:

let fac n =
  let rec loop i =
    if i >= n
    then i
    else i * loop (i+1)
  in
    loop 1

C'est un avant la récursivité et comme vous pouvez le voir il est légèrement plus lourd que l'arrière variante récursive, car cela nécessite une fonction d'assistance. Maintenant, ce n'est pas la queue récursive comme le dernier appel dans loop est la multiplication, pas la récursivité. Donc, pour rendre l'arrière-récursive, vous feriez quelque chose comme ceci:

let fac n =
  let rec loop acc i =
    if i >= n
    then acc
    else loop (i*acc) (i+1)
  in
    loop 1 1

Maintenant, c'est à la fois un avant la récursivité et d'une queue de récursivité parce que l'appel récursif est un) une queue-appel et b) s'appelle elle-même avec une plus grande valeur (i+1).

Par exemple, une fonction récursive build_word qui prend un char list et de les combiner à une chaîne, c'est à dire['f'; 'o'; 'o'] à chaîne "foo". Le processus d'induction peuvent être visualisées de cette façon:

build_word ['f'; 'o'; 'o']
"f" ^ (build_word ['o'; 'o'])
"f" ^ ("o" ^ (build_word ['o'])    //base case! return "o" and fold back
"f" ^ ("o" ^ ("o"))
"f" ^ ("oo")
"foo"

Que c'était normal de récursivité. Notez que chaque paire de parenthèses représente une nouvelle trame de pile ou de l'appel récursif. La solution à ce problème (c'est à dire "f", "fo", ou "foo") ne peut pas être tiré avant la fin de la récursivité (où la base de cas est rencontré). Ce n'est qu'à la dernière image de retour le dernier résultat de retour à la précédente avant que le "popping", et vice-versa.

En théorie, chaque appel crée un nouveau cadre de pile (ou de la portée, si vous voulez) pour maintenir le "lieu" de la fragmentation de la solution retournée et collectées vers le début. Cela peut conduit à stackoverflow (ce lien est une récursivité btw).

Un appel tail version ressemblerait à quelque chose comme ceci:

build_word ['f'; 'o'; 'o'] ""
build_word ['o'; 'o'], "f"
build_word ['o'] ("f" ^ "o")
build_word [] ("f" ^ "o" ^ "o")
"foo"

Ici, le résultat cumulé (souvent stocké dans une variable connue comme accumulator) est passé avant. Avec l'optimisation, la queue d'appel de ne pas avoir à créer un nouveau cadre de pile, car il n'a pas à maintenir les précédents. La solution est en train d'être résolu "en avant" plutôt que "à l'envers".

Voici les build_word fonctions en deux versions:

non-queue

let build_word chars = 
  match chars with
  | [] -> None
  | [c] -> Some Char.to_string c
  | hd :: tl -> build_word tl
;;

queue

let build_word ?(acc = "") chars =
  match chars with
  | [] -> None
  | [c] -> Some Char.to_string c
  | hd::tl -> build_word ~acc:(acc ^ Char.to_string hd) tl
;;

L'avant de la récursivité est bien expliqué dans la accepté de répondre par @sepp2k.