Aritmetica ricorsiva
Somma
Iterativa
M+N = M+1 ... +1 (N volte)
M+N = ((...((M+1)+1)...)+1)
Somma(M, N) = Successivo(Successivo(...Successivo(M)...))
Somma(M, N) = SuccessivoN(M)
M+N = ((...((M+1)+1)...)+1)
Somma(M, N) = Successivo(Successivo(...Successivo(M)...))
Somma(M, N) = SuccessivoN(M)
FUNZIONE somiter(INTERO m, INTERO n): INTERO
INIZIO
INTERO i
PER(i DA 1 a n PASSO +1)
INCREMENTA(m) // m = m+1 // m = SUCCESSIVO(m)
somiter = m
FINE
INIZIO
INTERO i
PER(i DA 1 a n PASSO +1)
INCREMENTA(m) // m = m+1 // m = SUCCESSIVO(m)
somiter = m
FINE
apri M dita della mano destra
apri N dita della mano sinistra
mentre la mano sinistra non è chiusa esegui
(
apri un dito a destra
chiudi un dito a sinistra
)
la risposta è nella mano destra
apri N dita della mano sinistra
mentre la mano sinistra non è chiusa esegui
(
apri un dito a destra
chiudi un dito a sinistra
)
la risposta è nella mano destra
FUNZIONE somiter(INTERO m, INTERO n): INTERO
INIZIO
MENTRE(n > 0)
INIZIO
INCREMENTA(m)
DECREMENTA(n)
FINE
somiter = m
FINE
INIZIO
MENTRE(n > 0)
INIZIO
INCREMENTA(m)
DECREMENTA(n)
FINE
somiter = m
FINE
FUNZIONE somiter(INTERO m, INTERO n): INTERO
INIZIO
INTERO i
PER(i DA n FINO A 1 PASSO -1)
INCREMENTA(m)
somiter = m
FINE
INIZIO
INTERO i
PER(i DA n FINO A 1 PASSO -1)
INCREMENTA(m)
somiter = m
FINE
Ricorsiva
- Somma(M, N) = M, per N = 0
- Somma(M, N) = 1+Somma(M, N-1), altrimenti
Esempio
M=5, N=3
Somma(5, 3) = 1+Somma(5, 2) = 1+7 = 8
Somma(5, 2) = 1+Somma(5, 1) = 1+6 = 7
Somma(5, 1) = 1+Somma(5, 0) = 1+5 = 6
Somma(5, 0) = 5
Somma(5, 2) = 1+Somma(5, 1) = 1+6 = 7
Somma(5, 1) = 1+Somma(5, 0) = 1+5 = 6
Somma(5, 0) = 5
FUNZIONE somiric(INTERO m, INTERO n): INTERO
INIZIO
SE(N == 0) ALLORA
somric = m
ALTRIMENTI
somric = 1+omric(m, n-1)
FINE
INIZIO
SE(N == 0) ALLORA
somric = m
ALTRIMENTI
somric = 1+omric(m, n-1)
FINE
Ricorsiva
- Somma(M, N) = M, per N = 0
- Somma(M, N) = Successivo(Somma(M, Precedente(N))), altrimenti
Esempio
M=5, N=3
Somma(5, 3) = Successivo(Somma(5, Precedente(3)) = Successivo(Somma(5, 2)) = Successivo(7) = 8
Somma(5, 2) = Successivo(Somma(5, Precedente(2)) = Successivo(Somma(5, 1)) = Successivo(6) = 7
Somma(5, 1) = Successivo(Somma(5, Precedente(1)) = Successivo(Somma(5, 0)) = Successivo(5) = 6
Somma(5, 0) = 5
Somma(5, 2) = Successivo(Somma(5, Precedente(2)) = Successivo(Somma(5, 1)) = Successivo(6) = 7
Somma(5, 1) = Successivo(Somma(5, Precedente(1)) = Successivo(Somma(5, 0)) = Successivo(5) = 6
Somma(5, 0) = 5
FUNZIONE somiric(INTERO m, INTERO n): INTERO
INIZIO
SE(N == 0) ALLORA
somric = m
ALTRIMENTI
somric = SUCCESSIVO(somric(m, PRECEDENTE(n)))
FINE
INIZIO
SE(N == 0) ALLORA
somric = m
ALTRIMENTI
somric = SUCCESSIVO(somric(m, PRECEDENTE(n)))
FINE
Ricorsiva
- Somma(M, N) = M, per N = 0
- Somma(M, N) = Somma(M+1, N-1), altrimenti
FUNZIONE somiric(INTERO m, INTERO n): INTERO
INIZIO
SE(N == 0) ALLORA
somric = m
ALTRIMENTI
somric = somric(m+1, n-1)
FINE
INIZIO
SE(N == 0) ALLORA
somric = m
ALTRIMENTI
somric = somric(m+1, n-1)
FINE
Ricorsiva
- Somma(M, N) = M, per N = 0
- Somma(M, N) = Somma(Successivo(M), Precedente(N)), altrimenti
Esempio
M=5, N=3
Somma(5, 3) = Somma(Successivo(5), Precedente(3)) = Somma(6, 2) = 8
Somma(6, 2) = Somma(Successivo(6), Precedente(2)) = Somma(7, 1) = 8
Somma(7, 1) = Somma(Successivo(7), Precedente(1)) = Somma(8, 0) = 8
Somma(8, 0) = 8
Somma(6, 2) = Somma(Successivo(6), Precedente(2)) = Somma(7, 1) = 8
Somma(7, 1) = Somma(Successivo(7), Precedente(1)) = Somma(8, 0) = 8
Somma(8, 0) = 8
FUNZIONE somric(INTERO m, INTERO m): INTERO
INIZIO
SE(n == 0) ALLORA
somric = m
ALTRIMENTI
somric = somric(SUCCESSIVO(m), PRECEDENTE(n))
FINE
INIZIO
SE(n == 0) ALLORA
somric = m
ALTRIMENTI
somric = somric(SUCCESSIVO(m), PRECEDENTE(n))
FINE
