SALI LA RICORSIONE

Talliente Martina

Conoscenza di algoritmi e funzioni. Si consiglia la visione dell’attività “Introduzione alle funzioni“

Sarebbe apprezzato aver svolto l’attività sugli algoritmi su https://programmailfuturo.it/come/primaria/lezioni-tradizionali/algoritmi/

Materiale

Scheda sulla ricorsione

Età

A partire da 9 anni

Numero di giocatori

Attività per tutta la classe

Competenze acquisite

Obiettivi di apprendimento al termine della classe terza della scuola primaria

Ambito algoritmi
O-P3-A-1. Riconoscere gli elementi algoritmici in operazioni abituali della vita quotidiana (p.es.: lavarsi i denti, vestirsi, uscire dall’aula…)

Ambito algoritmi
O-P3-A-2. Comprendere che problemi possono essere risolti mediante la loro scomposizione in parti più piccole

Obiettivi di apprendimento al termine della classe quinta della scuola primaria

Ambito algoritmi
O-P5-A-2. Risolvere problemi mediante la loro scomposizione in parti più piccole

Ambito algoritmi
O-P5-P-3. Riconoscere che una sequenza di istruzioni può essere considerata come un’unica azione oggetto di ripetizione o selezione

Anche una semplice situazione della vita quotidiana può essere tradotta in un’operazione ricorsiva.

Proietta o scrivi l’esempio di algoritmo ricorsivo sulla lavagna immaginando una scala formata da 5 gradini.

Leggi insieme alla classe gli algoritmi e aiuta a capire bene il funzionamento:

SALI LE SCALE{
	1. for(gradino=0; gradino<5; gradino+1)
		Sali 1 gradino
}

SALI_LE_SCALE(gradino){
	1. if(gradino=5) fermati
	2. else
		Sali 1 gradino
		SALI_LE_SCALE(gradino+1)
}

L’algoritmo iterativo dice che fin quando non siamo in cima alla scala dobbiamo salire 1 gradino. Il for significa che si parte dal gradino 0, cioè non siamo ancora saliti su nessun gradino, e fin quando gradino<5, ovvero fin quando non arriviamo all’ultimo gradino in cima alla scala, saliamo un gradino quindi gradino=0+1=1: siamo saliti sul primo gradino. Continuiamo perché non siamo arrivati all’ultimo gradino, quindi procediamo salendo ancora un gradino e gradino diventa 1+1=2: siamo saliti sul secondo gradino e così via.

Seguendo invece la soluzione ricorsiva, se siamo in cima alle scale ci fermiamo altrimenti saliamo 1 scalino e poi saliamo le scale. Infatti, si inizia con gradino=0 perché non siamo ancora saliti, siccome gradino è diverso da 5, saliamo un gradino e poi eseguiamo di nuovo SALI_LE_SCALE con gradino= 0+1: siccome gradino è 1 ed è diverso da 5 saliamo un altro gradino ed eseguiamo SALI_LE_SCALE con gradino= 1+1 = 2, siamo saliti sul secondo gradino e così via…
Questo metodo risolve il problema richiamando sé stesso. Ciò è possibile grazie al fatto che una rampa di scale può essere vista come la successione di un gradino e una rampa di scale più corta.

L’algoritmo è ricorsivo quando una sequenza di operazioni viene eseguita ripetutamente, su dati che cambiano ogni volta e danno un nuovo risultato ogni volta. Solitamente una determinata condizione fa terminare l’algoritmo.
Un algoritmo ricorsivo segue un approccio chiamato divide et impera: esso scompone il problema in sotto-problemi simili all’originale, per poi risolvere i sotto-problemi ricorsivamente.

Successivamente fai eseguire in pratica gli algoritmi ai bambini: dividi in gruppi da cinque e utilizza 5 gradini se possibile, altrimenti simula dei gradini utilizzando cerchi o segni a terra. Alla fine della scala, i bambini dovranno prendere un fazzoletto. Seguono dei nuovi algoritmi leggermente modificati (è stata solamente aggiunta l’istruzione di prendere il fazzoletto):

SALI LE SCALE{
	1. for(gradino=0; gradino<5; gradino+1)
		Sali 1 gradino
        2. prendi il fazzoletto 
}

SALI_LE_SCALE(gradino){
	1. if(gradino=5) prendi il fazzoletto
	2. else
		Sali 1 gradino
		SALI_LE_SCALE(gradino+1)
}

Quando i bambini eseguono l’algoritmo iterativo dovranno partire tutti insieme e salire contemporaneamente un gradino alla volta fin quando non si è arrivati in cima e uno di loro prenderà il fazzoletto.

Per eseguire il metodo ricorsivo invece, dovrà iniziare solo un bambino e un bambino per volta dovrà salire uno scalino: quando dovrà eseguire una nuova chiamata di funzione, richiederà a un compagno di eseguirla (quindi il compagno dovrà salire sul prossimo gradino). Il processo continua in questo modo, fino a quando un bambino si troverà nel caso base della funzione ricorsiva.
In quel momento si inverte la direzione del gioco: questo bambino, dopo aver preso il fazzoletto, lo dovrà passare al compagno che gli aveva chiesto di eseguire la chiamata di funzione, per poi tornare al proprio banco. La stessa cosa avverrà per tutti gli altri bambini fino al completamento.

Alla fine del gioco puoi stampare e distribuire la scheda sulla ricorsione a ogni bambino, lascia loro del tempo per provare a completarla da soli su quanto spiegato precedentemente. Se i bambini hanno difficoltà, ricopia il contenuto della scheda sulla lavagna, oppure proietta la scheda sulla lavagna, ed esegui il compito passo dopo passo insieme a loro.

Materiale aggiuntivo 1

Scheda sulla ricorsione.

Download