Funzione ricorsiva C ++

Un processo in cui una funzione specifica si definisce direttamente o indirettamente è noto per essere una ricorsione e che la rispettiva funzione è una funzione ricorsiva. Il processo di ricorsione si occupa dell'iterazione di più numeri alla stessa funzione. Per terminare l'esecuzione di un processo di ricorsione, dobbiamo avere un caso di base seguito da qualsiasi condizione. Questo tutorial utilizza il coinvolgimento delle funzioni di ricorsione in C ++, quindi prima di leggere questo, è necessario avere familiarità con le basi di questo linguaggio di programmazione.

La ricorsione è un approccio efficace per dissolvere i problemi come compiti complessi di calcoli matematici. Questo viene fatto distribuendo l'attività in sottosle. Questo processo viene eseguito seguendo la regola di divisione e conquista. Non è una cosa obbligatoria utilizzare sempre un processo di ricorsione nel programma per la ripetizione. Qualsiasi problema che viene risolto attraverso la ricorsione può anche essere risolto attraverso l'iterazione. Ma la funzione ricorsiva è più efficiente nella programmazione in quanto il codice è molto breve e facilmente comprensibile durante l'esecuzione dello stesso compito. Il processo di ricorsione è sempre raccomandato per problemi come la ricerca e l'ordinamento, gli attraversamenti degli alberi, ecc.

Nota: Il processo di ricorsione deve avere una condizione di terminazione o una classe di base. Nel secondo caso, porterà a esecuzioni infinite come un ciclo di iterazioni.

Sintassi della funzione ricorsiva (C ++)

La sintassi di base della funzione ricorsiva è data come:

void ricourse ()
// Dichiarazione (i)
ricorso();

Il concetto è di dividere un problema in molti problemi più piccoli e quindi aggiungere tutte le condizioni di base che possono fermare la ricorsione.

Condizione di base

In qualsiasi programma ricorsivo, la soluzione di un problema più grande è espressa in problemi più piccoli.

int fact (int n)

Se (n < = 1) // base case
Ritorno 1;
altro
'Altra affermazione'

La dichiarazione/condizione di 'n < =1' is defined here, and hence the larger value can be solved by converting to a smaller one until the condition of the base case is fulfilled. If we don't use a base condition in our program, then there will be no ending point specifying the code, the infinite execution will occur. Here we will use a sample example.

Funzione semplice

Ora considera un campione di una funzione ricorsiva in cui prendiamo un valore nel programma principale e quindi passiamo alla funzione. All'interno di una funzione, utilizziamo un'istruzione IF-ELSE. La parte "if" dell'istruzione si riferisce alla condizione di base per terminare la funzione o per limitare l'uscita. Questo verrà applicato quando il valore è inferiore a 1.

If (val < 1)

Mentre la caratteristica principale viene applicata sulla parte "altro" della funzione. Questa è la funzione ricorsiva.

# Funzione (val - 1)

Il valore viene visualizzato prima e dopo questa istruzione, quindi l'output conterrà i numeri in ordine decrescente e in ordine crescente. L'esecuzione del codice viene eseguita tramite un compilatore G ++. '-o' viene utilizzato per salvare l'output di un codice sorgente in un file di output.

$ g ++ -o r1 r1.C
$ ./R1

Ora, vogliamo vedere l'effetto della condizione di base in questo programma. Vedremo il valore risultante; Se rimuoviamo l'istruzione IF-ELSE dallo stesso programma sopra descritto, quale sarà l'output.

Puoi vedere che il resto del codice è invariato dopo aver rimosso l'istruzione condizionale. Dopo aver rimosso l'istruzione di base, l'output sembrerà l'immagine seguente. Non ci sarà endpoint definito per questa esecuzione. Puoi notare che l'output è una sorta di un singolo numero.

Questa stessa uscita dura molte righe fino a quando non viene mostrato un messaggio di dump core.

Funzionante di ricorsione

Supponiamo che un programmatore sia disposto a determinare la somma dei primi numeri N, ci sono molti modi per determinare la somma, ma il più semplice è aggiungere i numeri a partire da 1 a n. Quindi la funzione sembrerà così:

F (n) = 1+2+3+4+5+…+n

L'esempio sopra è la semplice aggiunta dei numeri. Il secondo approccio si occupa dell'uso di una funzione ricorsiva.

F (n) = 1 n = 1
F (n) = n + f (n-1) n> 1

Ora puoi sottolineare la differenza tra i due approcci. Nel secondo approccio, f () è una dissomiglianza di base, come viene chiamato.

La ricorsione è di due tipi. Uno è ricorsione diretta. Il secondo è una ricorsione indiretta. Una funzione viene chiamata un ricorsivo indiretto se ha una funzione di una funzione per un'altra funzione e che l'altra funzione chiama la prima funzione direttamente o indirettamente. Un campione per ricorsione diretta è illustrato come:

Int f (int n)
F (n);
// Qualche codice

Mentre un campione per la ricorsione indiretta è rappresentato come:

void f (int n)
f1 ();
void f1 (int n)
F();
ritorno;

Ora elaboreremo entrambi i tipi di funzioni ricorsive attraverso alcuni esempi di base.

Ricorsione diretta

Esempio 1

Questo esempio tratta il calcolo della serie Fibonacci. Ancora una volta il concetto è lo stesso; Un'affermazione condizionale viene utilizzata qui per fermare la condizione; Il valore dovrebbe essere uguale a zero. Altrimenti, se il valore è uguale a 1 o 2, restituirà 1. Poiché questa formazione di serie necessita di 2 numeri, quindi il numero utilizzato nel programma principale dovrebbe essere maggiore di 2. La formula di dichiarazione per il fibonacci è scritta nell'arte "else" della condizione. Questa è principalmente la ricorsione del programma.

# Funzione (val - 1) + funzione (val - 2))

Mentre la funzione principale inizierà la chiamata funzionale bypassing del valore. Questo valore è un numero fino al quale dovrebbe essere l'output. L'uscita può essere controllata tramite il terminale Linux da un compilatore G ++.

Esempio 2

Questo esempio tratta il calcolo fattoriale di un numero. Per questo calcolo, un numero deve essere maggiore di 1, quindi qui abbiamo applicato una condizione di base; Se questa parte dell'affermazione "if" è soddisfatta, il programma verrà terminato; Altrimenti, l'operazione matematica viene applicata al numero.

Val * funzione (val - 1)

Questa è la funzione di ricorsione, in cui la risposta della funzione viene nuovamente utilizzata nella chiamata della funzione.

Il valore risultante è mostrato di seguito.

Ricorsione indiretta

Applicheremo lo stesso calcolo di fattoriale indirettamente. Come abbiamo descritto in precedenza, che nella ricorsione indiretta, le funzioni non lo chiamano, quindi abbiamo bisogno di un'altra funzione a questo scopo. Fare un esempio che ha due funzioni. Nella funzione A, la funzione di ricorsione viene dichiarata allo stesso modo dell'esempio precedente, ma la chiamata di funzione è per la seconda funzione, funzione-B. La funzione B contiene lo stesso metodo di calcolo e contiene la richiesta ricorsiva per la funzione a.

Nel programma principale, viene effettuata una chiamata di funzione alla funzione A.

Quando vedi l'output, noterai che la risposta per entrambi i metodi di ricorsione è la stessa, ma solo la differenza è nell'approccio utilizzato.

Conclusione

"C ++ Funzione ricorsiva" presenta molti vantaggi in quanto viene utilizzato nei processi di ricerca e smistamento. La condizione di base ha il ruolo principale nell'esecuzione della ricorsione, in quanto limita l'output e l'esecuzione infinita. Gli esempi comunemente usati sono spiegati qui per fornire la comprensione dell'utente della ricorsione.