subroutine. ricorsione

Una procedura o una funzione può contenere una chiamata a un'altra procedura al suo interno. Compreso, la subroutine può chiamare se stessa. In questo caso, al computer non importa. Inoltre, come sempre, esegue costantemente i comandi che ha incontrato dall'alto verso il basso.

Se ricordi la matematica, allora lì puoi incontrare il principio dell'induzione matematica. È il seguente:

Una certa affermazione è vera per ogni naturale n if
    1. è valido per n = 1 e
    2. dalla validità dell'affermazione per qualsiasi n = k naturale arbitrario ne consegue che è vera per n = k+1.

In programmazione, questa tecnica è chiamata ricorsione

La ricorsione è un modo per definire un insieme di oggetti in termini dell'insieme stesso, basato su dati casi base semplici.

Ricorsivo sarà anche chiamato una procedura (funzione) che richiama se stessa direttamente o tramite altre procedure e funzioni
Un esempio di procedura ricorsiva:

procedura Rec(a: integer);
inizio
    se un > 0 allora
        Rec(a - 1);
    scrivere un);
fine;

Schematicamente, il lavoro di ricorsione può essere rappresentato da un diagramma di flusso

Abbiamo visto che la ricorsione è l'esecuzione ripetuta di istruzioni contenute in una subroutine. E questo, a sua volta, è simile al lavoro del ciclo. Esistono linguaggi di programmazione in cui il costrutto loop è del tutto assente, ad esempio Prolog. 
Proviamo a simulare il funzionamento del ciclo for. 
Il ciclo for contiene una variabile contapassi. In una subroutine ricorsiva, tale variabile può essere passata come parametro.

//LoopImitation() procedura con due parametri
//Primo parametro – contapassi, secondo parametro – numero totale di passi
procedura LoopImitation(i, n: intero);
inizio
    writeln('Ciao N ', io); // Operatore da ripetere per qualsiasi valore di i
    se io < n then //Fino a quando il contatore del ciclo diventa uguale al valore n,
        LoopImitation(i + 1, n); //chiama una nuova istanza della procedura, con il parametro i+1 (transizione al valore successivo i)
FINE; 

Iterazione nella programmazione — in senso lato — organizzazione del trattamento dei dati, in cui le azioni si ripetono molte volte, senza portare a chiamate a se stesse (a differenza di %BA%D1%83%D1%80%D1%81%D0%B8%D1%8F" title="Ricorsione" >Ricorsioni). In senso stretto — processo di elaborazione dei dati ciclico in un'unica fase. 
Spesso gli algoritmi iterativi nella fase corrente (iterazione) utilizzano il risultato della stessa operazione o azione calcolata nelle fasi precedenti.  Un esempio di tali calcoli è il calcolo delle relazioni di ricorrenza. 
Un semplice esempio di valore ricorsivo è il fattoriale: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\) Il calcolo del valore ad ogni passo (iterazione) è \(N=N \cdot i\) .  Quando calcoliamo il valore di \(N\), prendiamo il valore già memorizzato \(N\).

Il fattoriale di un numero può anche essere descritto usando la formula ricorrente:



Potresti notare che questa descrizione non è altro che una funzione ricorsiva.
Qui la prima riga (\(n <= 1\)) — questo è il caso base (condizione finale della ricorsione) e la seconda riga è la transizione al passaggio successivo. 
 

La funzione fattoriale ricorsiva sarebbe simile a questa	Confronta l'algoritmo per trovare il fattoriale nel solito modo non ricorsivo
funzione Fattoriale(n: intero): intero; iniziare     se n > 1 poi         Fattoriale := n * Fattoriale(n - 1)     altro         Fattoriale := 1; fine;	x := 1; for i := 2 an do     x := x * io; writeln(x);

Dovrebbe essere chiaro che le chiamate di funzione comportano un sovraccarico aggiuntivo, quindi un calcolo fattoriale non ricorsivo sarà leggermente più veloce. 
Conclusione: dove puoi scrivere un programma con un semplice algoritmo iterativo, senza ricorsione, allora devi scrivere senza ricorsione. Tuttavia, esiste un'ampia classe di problemi in cui il processo computazionale è implementato solo mediante ricorsione.
D'altra parte, gli algoritmi ricorsivi sono spesso più comprensibili.