•
Scrivere una funzione ricorsiva (in C) che calcoli la somma degli elementi di un array A[1..n] di n interi.
•
Soluzione:
Algoritmo ricorsivo
(Caso Base) Se l’array ` e vuoto (n=0) allora la somma dei suoi elementi ` e zero
(Passo generico) Se l’array [a
1, . . . , a
n] non ` e vuoto allora la
somma dei suoi elementi ` e data da a
npi´ u la somma degli
elementi di [a
1, . . . , a
n−1].
•
Scrivere una funzione ricorsiva (in C) che calcoli la somma degli elementi di un array A[1..n] di n ≥ 1 interi.
•
Soluzione:
int somma(int A[]; int n) {
if (n=0) return 0
else return A[n] + somma(a, n-1) end
Simulare su A = [2, 4, 7, 5], fornendo la sequenza delle chiamate
•
Scrivere un algoritmo ricorsivo per il calcolo del minimo in un array A[1..n] di n interi positivi.
•
Soluzione:
Algoritmo ricorsivo
(Caso Base) Se l’array non ` e vuoto e ha un solo elemento a, allora a ` e il minimo elemento.
(Passo generico) Se l’array contiene [a
1, . . . , a
n] e ha pi` u di un elemento, calcola il minimo degli elementi di
[a
1, . . . , a
n−1], sia min tale minimo.
Se a
n< min allora minimo = a
n, altrimenti minimo = min.
•
Scrivere una funzione ricorsiva (in C) che, avendo in input un array di n interi positivi, dia in output l’elemento minimo della lista.
•
Soluzione:
int minimo(int A[], int n)
if (n > 0) if [a[n] < minimo(a, n-1)) return A[n]
else return minimo(a, n-1) end
Simulare su A = [2, 4, 7, 5], fornendo la sequenza delle chiamate
•
Scrivere una funzione ricorsiva (in C) che, avendo in input un array di n interi di interi positivi, dia in output TRUE se 10 ` e un elemento della lista, FALSE altrimenti.
•
Soluzione:
Algoritmo ricorsivo
(Caso Base) Se l’array ` e vuoto allora 10 non ` e un elemento della lista
(Caso Base) Se l’array [a
1, . . . , a
n] non ` e vuoto e a
1= 10, allora 10 ` e un elemento della lista.
(Passo generico) Se l’array [a
1, . . . , a
n] non ` e vuoto e
a
16= 10, 10 ` e un elemento dell’array se e solo se 10 ` e un
elemento di [a
2, . . . , a
n].
•
Scrivere una funzione ricorsiva (in C) che, avendo in input un array di n interi di interi positivi, dia in output TRUE se 10 ` e un elemento della lista, FALSE altrimenti.
•
Soluzione:
Boolean cerca10(int A[], int n):
begin
if (n=0) return FALSE
else if (A[n]=10) return TRUE
else return cerca10(L^.prossimo) end
Simulare su A = [2, 4, 7, 5], fornendo la sequenza delle chiamate ricorsive.
Simulare su A = [2, 10, 7, 5], fornendo la sequenza delle chiamate
•
Scrivere una funzione ricorsiva (in C) che, avendo in input un array di n interi di interi positivi, dia in output TRUE se tutti gli elementi sono maggiori di 10, FALSE altrimenti.
•
Soluzione:
Algoritmo ricorsivo
(Caso Base) Se l’array ` e vuoto allora tutti gli elementi della lista sono maggiori di 10.
(Caso Base) Se l’array non ` e vuoto e se il primo elemento a dell’array ` e minore o uguale a 10, allora non tutti gli elementi della lista sono maggiori di 10.
(Passo generico) Se l’array [a
1, . . . , a
n] non ` e vuoto e se
a
1> 10, tutti gli elementi della lista sono maggiori di 10 se e
solo se tutti gli elementi della lista [a
2, . . . , a
n] sono maggiori
di 10.
•
Scrivere una funzione ricorsiva (in C) che, avendo in input un array di n interi di interi positivi, dia in output TRUE se tutti gli elementi sono maggiori di 10, FALSE altrimenti.
•
Soluzione:
boolean tutti(int A[], int n) if (n=0) return TRUE
else if (A[n] <= 10 ) return FALSE
else return tutti(A, n-1)
•
Scrivere una funzione ricorsiva (in C) POT (n) per il calcolo dei numeri F (n) definiti dalle seguenti relazioni:
F (1) = 2
F (n) = 2F (n − 1) n ≥ 2
Soluzione:
int POT(int n) {
if (n = 1) then return 2
else return 2*POT(n-1)
}
•
Scrivere una funzione ricorsiva (in C) TIME (n) per il calcolo dei numeri T (n) definiti dalle seguenti relazioni:
T (0) = 0, T (1) = 1
T (n) = 2T (n − 2) + 5 n ≥ 2
Soluzione:
int TIME(int n) {
if ( n = 0 ) return 0
else if (n = 1 ) return 1
else return 2 * TIME(n-2) + 5
•
Scrivere una funzione ricorsiva (in C) che, avendo in input un array di n interi non negativi, dia in output il numero degli elementi positivi della lista.
•
Scrivere una funzione ricorsiva (in C) TIME (n) per il calcolo dei numeri T (n) definiti dalle seguenti relazioni:
T (0) = 0, T (1) = 1
T (n) = 2T (n − 2) + T (n − 1) n ≥ 2
