Ceci est un post sur la recursion dans un post sur la recursion

On distingue deux formes de récursion : La recursion directe ou indirecte.

Dans la récursion directe (exemple en ruby)  la fonction s'appelle directement.

def facdir(n)
return 1 if n==1
return (n * facdir(n-1))
end


La fonction fac s'appelle en se transmettant le paremetre n-1

Dans la méthode indirecte , la fonction s'appelle aussi , mais elle va se transmettre son contexte
en plus de son parametre  normal.
Pour une fonction simple , le contexte sera limité à une variable destinée à accueillir le résultat.


Exemple :


def facind_r(n,prod)
return prod if n==1
return facind_r(n-1,n*prod)
end


La variable 'prod' est le 'contexte'.

L'appel de la fonction se fera par :

def facind(n)
    facind_r(n,1)
end



La méthode indirecte est meilleure que la méthode directe.
A l'appel d'une itération le système n'a pas besoin de mettre
dans la pile l'appel de la fonction CAR AUCUNE opération ne sera à réaliser à son retour.







En Haskell :


module Main where

 facdir :: Int -> Int 
 facdir 1 = 1
 facdir n = n * facdir(n-1)


 facind :: Int ->Int
 facind n = facind_r (n,1)

 facind_r :: (Int,Int)  -> Int 
 facind_r (1,prod) = prod
 facind_r (n,prod) = facind_r( n-1, n* prod )
 

En Erlang:

-module (fac2).
- export([facdir/1,facind/1]).

facdir(1) -> 1;
facdir(N) -> N * facdir(N-1).

facind(N) -> facind_r(N,1).
facind_r(1,Prod) -> Prod;
facind_r(N,Prod) -> facind_r(N-1,N*Prod).