Vi propongo di seguito alcuni esercizi sulla ricorsione svolti con il linguaggio Python. Per chi non sapesse cosa è esattamente la ricorsione potrete trovarlo cercando su WikiPedia è spiegato in maniera abbastanza esaustiva, altrimenti qualsiasi buon libro di Informatica potrà togliervi ogni dubbio. Nel caso foste delle persone veramente pigre vi dirò semplicemente che in informatica la ricorsione è il “richiamare” una funzione dentro se stessa fino a che non si ottiene il risultato cercato senza entrare in un ciclo infinito.
Un certo Peter Deutsch disse:
“L’iterazione è umana, la ricorsione è divina.”
Presto capirete perchè!
Inzialmente vedrete solo il testo dell’esercizio ma cliccando sul testo tra i bordi blu apparirà per magia anche la soluzione. Non è un caso che abbia nascosto la soluzione, potrebbe tornarvi utile sforzare la vostra mente prima di chiedere aiuto. :)
Alcuni dei seguenti esercizi sulla ricorsione presentano più di una soluzione in quanto la ricorsione NON ammette solo una soluzione ma ne posso esistere diverse, vediamo se trovate la vostra.
Le soluzioni degli esercizi sulla ricorsione proposti di seguito sono svolti in Python, voi potete utilizzare i testi degli esercizi e risolverli in qualsiasi altro linguaggio di programmazione, in quanto la ricorsione è un metodo matematico replicabile anche in altri ambienti e non appartiene solo al linguaggio Python.
Se siete interessati ad approfondire l’argomento, troverete altri articoli che trattano Python tramite dei video a questo link.
Spero di essere stato abbastanza chiaro nello spiegare l’argomento. A presto!
P.S.
Se notate qualche errore o imprecisione o sapete come migliorare le mie funzioni, non esitate a scrivermi commentando di seguito nell’apposito modulo a fine pagina oppure potere scrivermi privatamente dal modulo di contatto nella pagina Get In Touch e cercheremo di risolvere insieme il problema, ma non vi nascondo ovviamente che preferisco sempre condividere con le altre persone tutti i dibattiti in quanto si può imparare molto anche dagli errori altrui. Grazie!
Esercizi sulla ricorsione
Scrivere una funzione ricorsiva che, data una stringa s, restituisce vero se la stringa contiene solo coppie consecutive formate da una cifra numerica e un carattere alfabetico; falso altrimenti.
Nota: ricordare metodi isdigit() e isalpha() del di dato strutturato in python
Scrivere una funzione ricorsiva booleana che, data una stringa s, una stringa c di lunghezza 1, e un intero n, restituisce il valore vero se c è presente ALMENO n volte nella stringa s, falso altrimenti.
Scrivere una funzione ricorsiva che data un stringa s restituisca la stringa ottenuta da s eliminando le vocali.Ad esempio l’invocazione eliminaVocali(‘pippo’) deve restituire la stringa ‘ppp’.
Scrivere una funzione ricorsiva che, data una stringa s, restituisce come risultato una stringa ottenuta elimanando da s tutti i caratteri ripetuti consecutivamente, tranne il primo (Es.: se s = ‘aaabbcccc’ la funzione deve restituire ‘abc’; se s = ‘ababcc’ la funzione deve restituire ‘ababc’.
Scrivere una funzione ricorsiva che data una lista di interi l restituisce la somma dei soli numeri pari.
Scrivere una funzione ricorsiva che, data una lista di numeri interi (positivi o negativi), restituisce come risultato il valore vero se la somma dei numeri contenuti nella lista è un valori pari, falso altrimenti. Se la lista è vuota, la funzione restituisce il valore vero.
Scrivere un funzione ricorsiva che data una stringa s controlli se la lista divisa a metà abbia la prima parte uguale alla seconda, se la lista dovesse essere dispara l’ultimo elemento può essere trascurato. Es. s = s1 + s2 – s1 = s2
Scrivere una funzione ricorsiva che, dato una lista di interi l, restituisca una nuova lista di interi ottenuto da l sostituendo ogni numero negativo con 0. Ad esempio l’invocazione azzeraNegativi({1,-2, 3, 4, -5}), deve restituire l’array {1, 0, 3, 4, 0}.
Scrivere una funzione ricorsiva che data una stringa s, restituisca una stringa costituita dai caratteri di s invertiti. Ad esempio l’invocazione reverse(‘pippo’) deve restituire la stringa ‘oppip’.
Scrivere una funzione ricorsiva che data un stringa s, restituisca una stringa ottenuta da s sostituendo ogni spazio bianco con il carattere underscore (‘_’).
Ad esempio l’invocazione underscore(‘pippo e topolino’) deve restituire la stringa ‘pippo_e_topolino’.
Si definisca una funzione ricorsiva che, data una lista di stringhe e una stringa x di un carattere, restituisce true se almeno una di queste stringhe contiene il carattere specificato da x, e false altrimenti.
Si definisca una funzione ricorsiva che, data una lista di interi l, e un valore intero x, verifica che la lista goda della seguente proprietà:
Nota: se la lista è di lunghezza dispari, il valore dell’elemento centrale è ininfluente.
Si definisca una funzione ricorsiva che, data una lista L, un valore V e un intero k, restituisce true se il valore V è presente in tutte le posizioni della lista il cui indice è multiplo di k, e false altrimenti.
Scrivere una funzione ricorsiva che data una lista di interi restituisce la lista ordinata dall’elemento più piccolo a quello più grande.
Assegnato un vettore F di float di dimensione N, scrivere una funzione ricorsiva che calcoli il massimo valore tra la somma di ogni elemento con il successivo ( escluso l’ultimo )
Assegnata una stringa S ed un carattere c, scrivere una funzione ricorsiva che calcoli le occorrenze di c in S
Sia assegnato un vettore A di interi di dimensione N. Scrivere una funzione ricorsiva che calcoli il massimo valore degli elementi di A.
Definire una funzione ricorsiva che data una stringa s resituisce vero se la stringa e composta dallo stesso numero di caratteri numerici e alfabetici falso altrimenti
Scrivere una funzione ricorsiva che, assegnati due interi N1 ed N2, restituisca la somma di tutti gli interi compresi tra N1 ed N2
Scrivere e una funzione ricorsiva che stampi il contenuto di una lista.
Definire una funzione ricorsiva che data una stringa restituisca ogni elemento delle stringa diviso dagli altri da uno spazio. Es. ‘abcd’ diventa ‘a b c b’.
Se ti è piaciuto questo articolo o ti è stato utile in qualche modo, lascia un commento, condividilo con i tuoi amici e seguimi sui social.
-
I miei hosting preferiti
- L'hosting specializzato per WordPress che utilizzo di più che ha tutto il necessario: SiteGround
- L'hosting specializzato per WordPress con delle SUPER performance ed il miglior servizio clienti di sempre: Kinsta
-
Ti interessa il mondo delle crypto monete come Bitcoin? Ricevi dei bonus utilizzando i link qui sotto
- Il più grande exchange al mondo quotato a Wall Street ( Ottieni un bonus di 10$ in Bitcoin ): Coinbase
- La crypto App con una crescita esponenziale che permette lo scambio di tantissime monete ( Ottieni un bonus di 25$): crypto.com
- Scambia la maggior parte delle crypto in un batter d'occhio (Ottieni un bonus): Binance
- Ottieni interessi depositando le tue crypto: BlockFi
- Puoi ricevere gli interessi più alti del mercato (più un bonus di benvenuto di 10$ in Bitcoin): NEXO
-
Carte gratuite
- Carta e conto gratuiti con IBAN italiano: N26
l’esercizio “Si definisca una funzione ricorsiva che, data una lista L, un valore V e un intero k, restituisce true se il valore V è presente in tutte le posizioni della lista il cui indice è multiplo di k, e false altrimenti.” è incorretto.
la giusta soluzione è:
def check(L, V, k):
# @Param L: list
# @Param V: value
# @Param k: index
if k>len(L):
return true
if L[k]== V:
return check(L[k:], V, k)
else:
return false
Grazie per la segnalazione!
vorrei proporre una diversa soluzione del problema “Scrivere una funzione ricorsiva che data una stringa s, restituisca una stringa costituita dai caratteri di s invertiti. Ad esempio l’invocazione reverse(‘pippo’) deve restituire la stringa ‘oppip’. ” :
def FuncRic9(s):
# @param s : String
if len(s) <= 1 :
return s
return FuncRic9(s[1:]) + s[0]
Vorrei proporre una soluzione diversa e più corta di quella proposta da voi dell’esercizio seguente “Scrivere una funzione ricorsiva che data una lista di interi restituisce la lista ordinata dall’elemento più piccolo a quello più grande.” ecco il codice :
def FuncRic14(l):
# @param l : List
if len(l) == 0 :
return []
min = l[0]
for i in range(len(l)):
if l[i] < min :
min = l[i]
l.remove(min)
return [min] + FuncRic14(l)
Vorrei proporre una soluzione ottimale all’esercizio “Assegnata una stringa S ed un carattere c, scrivere una funzione ricorsiva che calcoli le occorrenze di c in S” con il seguente codice:
def FuncRic16(S,c):
# @param S : String
# @param c : String
if len(S) == 0:
return 0
if S[0] == c :
return 1 + FuncRic16(S[1:],c)
else:
return FuncRic16(S[1:],c)
Vorrei far notare che le soluzioni dell esercizio “Scrivere una funzione ricorsiva che, assegnati due interi N1 ed N2, restituisca la somma di tutti gli interi compresi tra N1 ed N2 ” sono sbagliate, dato che la penultima somma non la contano, quando andrebbe contata. Quindi al posto di ” if a == b-1 return false” non ci si dovrebbe mettere niente dato che il false in valori numerici vale 0.
“Scrivere un funzione ricorsiva che data una stringa s controlli se la lista divisa a metà abbia la prima parte uguale alla seconda, se la lista dovesse essere dispara l’ultimo elemento può essere trascurato. Es. s = s1 + s2 – s1 = s2”
Voglio far notare che <> non è corretto in quanto (len(s)/2)+1 restituirà un numero con la virgola.
Posto la mia soluzione:
def uguaglianza_stringa(s):
if len(s)%2!=0:
s=s[:len(s)-1]
if len(s)==0:
return True
mid_length=len(s)//2
if s[0]!=s[mid_length]:
return False
else:
return uguaglianza_stringa(s[1:mid_length]+s[mid_length+1:])
non riesco a vedere le soluzioni
scusi, non riesco a visualizzare le soluzioni
può essere accettata come soluzione al problema 17?
def maxNList(L):
if len(L)==1:
return L[0]
else:
L[1]=max(L[0],L[1])
return maxNList(L[1:])