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 = 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:
void Rec(int a)
{
if (a>0) Rec(a-1);
cout << UN;
}
Schematicamente, il lavoro di ricorsione può essere rappresentato da un diagramma di flusso
La procedura Rec() viene eseguita con parametro 3. Poi, 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 la procedura con parametro 0 viene chiamato il parametro 0, la chiamata ricorsiva già non avverrà e la procedura con il parametro 0 stamperà il numero 0 e terminerà. 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.
|
Ricorsione. Simulazione del ciclo
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 lavoro del ciclo for.
Il ciclo for contiene una variabile contapassi. In una subroutine ricorsiva, tale variabile può essere passata come parametro.
// Procedura LoopImitation() con due parametri.
// Primo parametro – contapassi, secondo parametro – numero totale di passi.
void LoopImitation(int i, int n)
{
cout << "Ciao N" << io << finel; // Operatore da ripetere per qualsiasi valore di i
if (i < n) // Fino a quando il contatore del ciclo è uguale a n,
{ // chiama una nuova istanza della procedura, con il parametro i+1 (passa al valore successivo i).
LoopImitation(i + 1, n);
}
}
|
Ricorsione e iterazione
Per capire la ricorsione, devi capire la ricorsione...
Iterazione nella programmazione: una fasedi un processo ciclico di elaborazione dei dati.
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:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{casi} \end{equazione*}\)
Potresti notare che questa descrizione non è altro che una funzione ricorsiva.
Qui la prima riga ( \(n <= 1\)) è il caso base (condizione di terminazione della ricorsione) e la seconda riga è la transizione al passo successivo.
| Funzione fattoriale ricorsiva |
Algoritmo iterativo |
|
int Fattoriale(int n)
{
se (n > 1)
return n * Fattoriale(n - 1);
altrimenti restituisce 1;
}
|
x = 1;
per (i = 2; i <= n; i++)
x = x * io;
cout << 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.
|
Attività
Nell'alfabeto della lingua della tribù "Tumba-Yumba"; quattro lettere: "K", "L", "M" e "N". Devi visualizzare tutte le parole costituite da n lettere che possono essere costruite dalle lettere di questo alfabeto.
Il problema è un normale problema di forza bruta che può essere ridotto a un problema minore.
Sostituiremo in sequenza le lettere per la parola.
La prima posizione di una parola può essere una delle 4 lettere dell'alfabeto (K. L, M, N).
Mettiamo prima la lettera K. Quindi, per ottenere tutte le varianti con la prima lettera K, devi enumerare tutte le possibili combinazioni di lettere nelle rimanenti posizioni n - 1 e così via. (vedi foto).
 Quindi, il problema si riduce a risolvere quattro problemi di lunghezza n - 1.
Itera su n caratteri in modo ricorsivo
w[0]='K'; // itera sugli ultimi caratteri L-1
w[0]='L'; // itera sugli ultimi caratteri L-1
w[0]='M'; // itera sugli ultimi caratteri L-1
w[0]='N'; // itera sugli ultimi caratteri L-1
w - una stringa di caratteri che memorizza la parola di lavoro.
Così, abbiamo ottenuto la ricorsività. Possiamo organizzare la soluzione del problema sotto forma di una procedura ricorsiva.
Resta da determinare quando finirà la ricorsione? Quando tutti i caratteri sono impostati, cioè, il numero di caratteri impostati è n. In questo caso è necessario visualizzare sullo schermo la parola risultante ed uscire dalla procedura.
Il programma C++ avrà questo aspetto.
#include<iostream>
utilizzando lo spazio dei nomi std;
void TumbaWords( stringa A, stringa &w, int N )
// w - parametro modificabile (risultato stringa)
// Alla procedura TumbaWords viene passato l'alfabeto come stringa di caratteri,
// la parola parola e il numero di caratteri già impostati (precedenti – 0).
{
int io;
if (N == w.size())
{
// se tutti i caratteri sono già stati impostati sulla parola,
// quindi è necessario emettere una stringa e terminare la procedura
cout << con<< finel;
ritorno;
}
for ( i = 1; i < A.size(); i ++ )
{
// se la condizione sopra è falsa (ovvero, non tutti i caratteri sono spaziati,
// quindi nel ciclo passiamo attraverso tutti i caratteri dell'alfabeto e
// metti alternativamente il carattere nel primo spazio libero
w[N] = A[i];
TumbaParole ( A, w, N+1 );
}
}
principale()
{
int;
parola stringa;
int;
cin>> N;
parola.resize(n); // aumenta la stringa alla dimensione n
TumbaWords("KLMN", parola, 0 );
}
NOTA che w è un parametro mutabile (stringa di risultato)!
|