La funzione ricorsiva nel linguaggio C con l'uso dei vettori

ESERCIZI (RICORSIONE)

Esercizi

• 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 [a1 , . . . , an ] non `e vuoto allora la somma dei suoi elementi `e data da an piu ́ la somma degli elementi di [a1, . . . , an−1].

Esercizi

• 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 ricorsive.

Esercizi

• 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 [a1 , . . . , an ] e ha piu` di un elemento, calcola il minimo degli elementi di
[a1, . . . , an−1], sia min tale minimo.
Se an < min allora minimo = an, altrimenti minimo = min.

Esercizi

• 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 ricorsive.

Esercizi

• 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 [a1,...,an] non `e vuoto e a1 = 10, allora 10 `e un elemento della lista. (Passo generico) Se l’array [a1 , . . . , an ] non `e vuoto e a1 = 10, 10 `e un elemento dell’array se e solo se 10 `e un elemento di [a2, . . . , an].

Esercizi

• 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 ricorsive.

Esercizi

• 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 [a1, . . . , an] non `e vuoto e se a1 > 10, tutti gli elementi della lista sono maggiori di 10 se e solo se tutti gli elementi della lista [a2 , . . . , an ] sono maggiori di 10.

Esercizi

• 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) end

Esercizi

• 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)thenreturn 2 else return 2*POT(n-1) }

Esercizi

• 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)return0 elseif(n=1)return 1 else return 2 * TIME(n-2) + 5 }

fonte: http://www.di.unisa.it/professori/lg/VCA/SLIDES/PISlideEserRic-array.pdf