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:
qualche affermazione è vera per ogni naturale
n if
1. è valido per
n = 1 e
2. dalla validità dell'affermazione per qualsiasi
n = knaturale 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, sulla base di dati casi base semplici.
Ricorsivo è una procedura (funzione) che chiama se stessa direttamente o tramite altre procedure e funzioni.
Esempio
def Rec(a):
if (a>0): Rec(a-1)
stampa(a)
Schematicamente, il lavoro di ricorsione può essere rappresentato da un diagramma di flusso
La procedura Rec() viene eseguita con parametro 3. Quindi, all'interno della procedura con parametro 3, viene chiamata la procedura con parametro 2, e così via, fino a quando viene chiamata la procedura con parametro 0. Quando viene chiamata la procedura con parametro 0, la chiamata ricorsiva non avverrà più e la procedura con parametro 0 stamperà il numero 0 ed uscirà. Poi il controllo viene ritrasferito alla procedura con il parametro 1, anch'essa termina il suo lavoro stampando il numero 1, e così via. prima della procedura con parametro 3.
Tutte le procedure chiamate vengono archiviate in memoria finché non completano il loro lavoro. Il numero di procedure concorrenti è chiamato
profondità di ricorsione.