“Ogni algoritmo ricorsivo è iterativo”. Potrebbe fornirmi il ragionamento (la dimostrazione ) di questa proposizione e un contresempio che dimostri che non vale il viceversa? cioè un esempio di algoritmo iterativo ma non ricorsivo?

Ricordiamo brevemente la definizione di un algoritmo ricorsivo: è un algoritmo che è definito in termini di se stesso; è composto da un passo induttivo e da una condizione di chiusura.

Il passo induttivo definisce una funzione per un generico valore di una variabile n in termini della funzione di n-1. La condizione di chiusura definisce la funzione in n=0. E allora chiamando la funzione per un valore si possono calcolare in cascata tutti i risultati intermedi fino a n=0.

Un tipico algoritmo che è facilmente espresso in forma ricorsiva è la definizione di fattoriale:

integer f=fatt(n)
{
    if n==0
        f=1;  /* condizione di chiusura */
    else
        f=n*fatt(n-1);    /* passo induttivo */
    end
    return(f);
}

Sviluppando passo per passo ad esempio il fattoriale di 5 si ha:

fatt(5) =5*fatt(4)
    =5*4*fatt(3)
    =5*4*3*fatt(2)
    =5*4*3*2*fatt(1)
    =5*4*3*2*1*fatt(0)
    =5*4*3*2*1*1=5!

La ricorsione pur permettendo codici molto compatti ed eleganti è di solito poco efficiente perché ogni funzione chiamata alloca memoria nello stack. Quindi è possibile, se non consigliabile, trasformare l’algoritmo in forma iterativa. Nel caso del fattoriale si ha

integer f=fattoriale(n)
{
    f=1;
    for i=1:n
        f=f*i;
    end
    return(f)
}

Vale anche il viceversa. Prendiamo un qualunque algoritmo iterativo:

for i=1:N
{
    blocco istruzioni;
}
end

posso definire una funzione ricorsiva

void ciclo(integer i)
{
    if i>N
        /* condizione di uscita */
        return;
    else
        blocco istruzioni;
        ciclo(i+1);
    end
}

Naturalmente a seconda del ciclo dovrò scegliere opportunamente la condizione di chiusura.