Ricorsione

Fattoriale

02/11/202102/11/2021 di admin

Definizione Formulazione Esempio Ricorsiva oppure

5!=5*4!

4!=4*3!

3!=3*2!

2!=2*1!

1!=1

2!=2*1=2

3!=3*2=6

4!=4*6=24

5!=5*24=120

Iterativa

1	5!=54321=120

La funzione fattoriale è presente in molti linguaggi / applicazioni Calc/Excel: FATTORIALE(x) Octave: factorial(x) Python: math.factorial(x) Quando non è presente è necessario codificarla. Approssimazione Per n molto grande si può rinunciare al valore esatto e utilizzare la formula di Stirling Conclusioni Metodo Pro Contro Ricorsivo Formulazione molto … Leggi tutto

Numeri di Fibonacci

02/11/202102/11/2021 di admin

I numeri di Fibonacci prendono il nome da una sfida matematica che Fibonacci lanciò a un suo collega. Il problema tratta la proverbiale velocità con cui i conigli si riproducono: il 1° mese è presente una coppia di conigli una coppia di conigli diventa matura all’inizio del 2° mese di vita la gestazione dura un … Leggi tutto

Hanoi

13/02/201811/02/2018 di admin

Vedi la discussione Algoritmo ricorsivo…

START

QUERY "Quanti dischi? ", n

CALL hanoi(n,1,2,3)

END

ENTER n,a,b,c

IF n = 1 THEN

WRITE a, "-->", c

ELSE

CALL hanoi(n-1,a,c,b)

CALL hanoi(1,a,b,c)

CALL hanoi(n-1,b,a,c)

ENDIF

RETURN

Fibonacci

28/02/201810/02/2018 di admin

Vedi la discussione Versione ricorsiva…

START

QUERY "n = ", n

fn=fibonacci(n)

WRITE "Fibonacci di", n, "=", fn

END

ENTER n

IF n <= 2 THEN

f=1

ELSE

f=fibonacci(n-1)+fibonacci(n-2)

ENDIF

RETURN f

Versione iterativa

START

QUERY "n = ", n

a=1

b=1

IF n >= 3 THEN

FOR i=3 TO n STEP 1 DO

c=a+b

a=b

b=c

ENDFOR

ENDIF

WRITE b

END

02/03/201705/05/2015 di admin

Se il linguaggio di programmazione prevede la ricorsione… una SUB A può chiamare la SUB A, se stessa, per svolgere lo stesso compito ma con un’stanza diversa La SUB A chiama la SUB A … finché non succede qualcosa (l’istanza diventa un caso particolare che non necessita di un’ulteriore chiamata ricorsiva) e si ritorna all’indietro … Leggi tutto