Ricorsione

Ricorsione

Definizione: “La ricorsione è un procedimento tramite cui definiamo un’entità in termini di sè

stessa.”

Esempi:

• broccolo romanesco

• triangolo di Sierpinsky

• fotografia con all’interno uno specchio

Usiamo la ricorsività anche in matematica, ad esempio per il fattoriale o per le prove per

induzione.

Dato che la ricorsione esiste nella natura, nella realtà, è necessario introdurla anche nei

linguaggi di programmazione.

La ricorsività in C è definita come una funzione che invoca sé stessa. Nella pratica, abbiamo

bisogno di alcuni elementi:

• Caso base, di partenza: ad esempio per il fattoriale 0!=1 oppure x0 = 1

• Passo ricorsivo: la funzione chiama sé stessa, sempre per il fattoriale: n! = n*(n-1)!

• Costruzione della soluzione: costruiamo la soluzione sulla base della chiamata delle n

ricorsioni, fino ad arrivare al caso base, nel caso del fattoriale, n(n-1)(n-2)*....*0!

Uso della memoria nella programmazione ricorsiva:

• La programmazione ricorsiva comporta spesso un uso inefficiente della memoria per

la gestione degli spazi di lavoro delle chiamate generate

• In alcuni casi viene comunque preferita ad altri approcci per la sua eleganza e

semplicità

• In altri casi su può ricorrere ad implementazioni iterative

lo fattoriale

= base 81071

casa

Ricorsione ) 1)

glu

glu n

= -

In C : iterazione

che gia visto

iterativa avevamo

soluzione

distingue con

fattoriale

si da

[ ,

include tdio.li

# > ( )

int

int fattoriale ricorsiva n ;

-

)

(

int )

main

int 8;

num ,

i " "

Tod )

&

(

sceaug num ;

, )

(

fattoriale ricorsivo

lo ;

num

= _ "

d )

" % 8

(

printf & ; #

, }

& fattoriale ricorsivo

i _

(a)

! n }

fattoriale D= Si

(

ricorsivo

1. ←

- :

fattore

return :

0 ; -1-1=1

} (1)

1

fattoriale (1)

2. ricorsivo = '

- ÷

2.1=2

= (2)

n

"

"

i. ÷ ÷ .

- (2)

fattoriale ricorsivo

3. Se

= 6

c-

- fattoriale ricorsivo

int fr 3.2=6

; = _

(3)

}

)

(

if -0

n = f

In 1 ;

_-

} 3

}

che )

(

fattoriale ricorsivo

fren 1

* ;

n -

_

} fr

return ;

} scriverlo

modo più di

Esiste compatto :

un }

)

( modo

fatt nic questo

int

int i