Descrivere una procedura ricorsiva che calcoli l'n-esimo elemento della successione di Fibonacci.

2

Il M.C.D.(a,b) può essere calcolato con un procedimento ricorsivo basato sulle seguenti relazioni:

1. se a>b

2. allora M.C.D.(a,b)=M.C.D.(a-b,b);

3. (a,b)=M.C.D.(b,a);

4. (a,a)=a.

Descrivere una procedura ricorsiva, basata sulle relazioni precedenti, che calcoli M.C.D.(a,b).

L'algoritmo di ricerca binaria si presta anche ad una realizzazione come procedura ricorsiva. Infatti il processo di suddivisione della tabella può essere applicato ricorsivamente alle varie sottotabelle individuate fino a quando la sottotabella non si riduce ad un unico elemento. Scrivere una tale procedura tenendo conto delle seguenti convenzioni: la chiave da ricercare è K, l'insieme su cui operare è un vettore V di N elementi, i limiti inferiore e superiore della sottotabella individuata sono indicati da t e u rispettivamente.

Scrivere un programma per il calcolo del fattoriale di un numero (con 0!=1 per definizione) in modo ricorsivo.

Definizione ricorsiva dei coefficienti binomiali.

Definiamo per n e k interi,

si chiama coefficiente binomiale.

Ad esempio


Dare una definizione per ricorrenza di , con n fissato e scrivere un programma basato su tale definizione.
 

Scrivere un programma che calcoli la somma di due interi x e y in modo ricorsivo come segue:

a] x + 0 • x

b] x + (y+1) = (x+y) + 1.

Scrivere un programma che calcoli il prodotto di due interi x e y in modo ricorsivo come segue:

a] x • 0 = 0

b] x • (y+1) = x • y + x.

Scrivere un programma che calcoli la potenza di un intero x elevato ad un altro intero y in modo ricorsivo come segue:

a] x0 = 1

b] xy+1 = xy • x.

La letteratura popolare riporta questa filastrocca:

"C'era una volta un re, seduto su un sofà,

che disse alla sua serva: "Raccontami una storia! "

E la serva cominciò:

"C'era una volta un re, seduto su un sofà,

che disse alla sua serva: "Raccontami una storia!"

E la serva cominciò:

"C'era una volta un re, .....

Si vuole una procedura ricorsiva per la stampa della filastrocca; poiché‚ tale procedura non ha, evidentemente, condizioni di terminazione, prevedere l'introduzione di un parametro che permetta la conclusione del racconto.

Scrivere una function ricorsiva che stabilisca se una data stringa è palindroma. Un stringa è palindroma quando risulta uguale al suo rovesciamento.

Esempi: 'AMA', 'ESSE', ...

Scrivere una function ricorsiva che effettui la ricerca binaria su una sequenza vettoriale ordinata A[INF..SUP].

Scrivere una function ricorsiva che calcoli il prodotto di due numeri naturali tenendo presente che si dispone soltanto dell'operazione di somma, di moltiplicazione per 2 e di divisione per 2.