Esercizi sulla ricorsione svolti in Python

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.

10 risposte per “Esercizi sulla ricorsione svolti in Python

  1. 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

  2. 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]

  3. 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)

  4. 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)

  5. 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.

  6. “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:])

  7. 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:])

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.