Una buona banca di soluzioni di ricorsione in C/C++/Java/C#

Question

Ho visto this question, ma le risposte non sono molto pertinenti. Un amico ha bisogno di una banca di problemi di ricorsione risolti per aiutarlo a studiare per un test domani.

Ha appreso il problema in teoria, ma ha problemi a capire come risolvere effettivamente i problemi di ricorsione. Conoscete una buona fonte di problemi di ricorsione risolti (preferibilmente in C, ma può essere anche in un linguaggio in stile C) disponibili in rete?

Nota: esempi in lingue funzionali non sono di grande aiuto in questo caso. Il mio amico è in una gara di studio per passare la sua prova domani, e sono sicuro che il cambio di lingua lo confonderà a questo punto (potrebbe essere educativo su altri tempi meno stressati).

Answer 1

This article spiega ricorsione e ha alcuni semplici esempi C per attraversare lista linkata e albero binario

Answer 2

Uno dei modi migliori per imparare la ricorsione è quello di acquisire esperienza in un linguaggio di programmazione funzionale come Haskell o Lisp o Scheme.

Quindi trovare i problemi ricorsivi può essere ridotto alla ricerca di alcuni problemi e risposte relative ai linguaggi di programmazione funzionale. Ecco un esempio 99 lisp problems.

Ci vogliono davvero solo 5 minuti per apprendere Scheme o Lisp in modo da poter iniziare subito con degli esempi per il test che hai menzionato domani.

Un altro ottimo modo per imparare la ricorsione è quello di ottenere un po 'di pratica in prove matematiche che coinvolgono l'induzione.

---

I concetti chiave relativi alla ricorsione:

Con la ricorsione non hai bisogno di sapere come risolvere il problema. Hai solo bisogno di sapere 2 cose. 1) come risolvere la più piccola istanza del problema e 2) come suddividerla in parti più piccole.

Equivalentemente, è sufficiente tenere presente che è necessario: 1) un caso base e 2) un caso ricorsivo.

Il caso base gestisce 1 singola istanza di ciò che si desidera fare con il più piccolo input.

Il caso ricorsivo suddivide il problema in un sottoproblema. Alla fine questo sottoproblema si ridurrà al caso base.

Esempio:

//1+...+n = n*n(+1)/2 = sumAll(n): 

int sumAll(int x) 
{ 
    if(x == 0) //base case 
    return 0; 
    else 
    return sumAll(x-1) + x; //recursive case 
} 

È importante comprendere che il caso base non è difficile capire. Deve solo esistere. Ecco una soluzione equivalente per x> 0:

//1+...+n = n*n(+1)/2 = sumAll(n): 
int sumAll(int x) 
{ 
    if(x == 1) //base case 
    return 1; 
    else 
    return sumAll(x-1) + x; //recursive case 
} 

Answer 3

Ciò sta andando a suonare come una risposta molto zoppo, ma la ricorsione è un paradigma che è spesso molto difficile da afferrare al primo per i principianti. Ci vorrà più di una giornata di meditazione sull'argomento affinché il tuo amico possa afferrare saldamente il concetto.

Si consiglia di farlo esaminare Project Euler per una direzione potenziale da studiare.

Answer 4

Penso che la sintassi di Haskell sia ottima per pensare in modo ricorsivo, perché il costrutto di corrispondenza del modello rende il caso base e il caso ricorsivo così ovvi. La traduzione di questo in un'altra lingua è quindi abbastanza semplice.

sumAll [] = 0 
sumAll (x:xs) = x + sumAll xs 

Per capire questo, è davvero solo bisogno di sapere che

• [] rappresenta un elenco vuoto,
• (x: xs) divide la lista in una testa (x) e una tail (xs)

Non hai bisogno di imparare tutto Haskell (che è, diciamocelo, difficile) - ma fare alcune delle nozioni di base ti aiuta sicuramente a pensare in ricorsione.

Answer 5

Leggi SICP (Struttura e Interpretazione dei programmi per computer)

Answer 6

#include<iostream> 
using namesspace std; 
int E(int x); 
int main() 
{ 
    int x; 
    cout << E(x) << endl; 
    return 0; 
} 

int E(int x) 
{ 
    return x ? (x % 10 + E(x/10)) : 0; 
} 

Answer 7

in C/C++ linguaggio una funzione può chiamare stesso e questo caso è chiamato ricorsione. Principalmente la ricorsione ha due casi:

1. caso base.
2. caso ricorsivo.

e abbiamo alcune categorie ricorsive come come ...

1. Liner ricorsione
2. ricorsione binario
3. ricorsione annidata
4. ricorsione mutua
5. ricorsione in coda

Ecco un esempio per discutere la ricorsione ...

// a recursive program to calculate NcR // 
#include <stdio.h> 
int ncr(int x,int y) 
{ 
    if(y>x) 
    { 
     printf("!sorry,the operation can't processed."); 
     getch(); 
     exit(1); 
    } 
    else if(y==0 ||y==x) //base case 
    { 
     return(1); 
    } 
    else 
    { 
     return(ncr(x-1,y-1)+ncr(x-1,y)); //recursive case 
    } 
}