Tail recursion: esempio
Scrivere una funzione ricorsiva che, dato un array
ordinato di interi, determini se l’intero x è presente
nell’array.
int ricerca_lineare(int *array, int a, int b, int x)
{
int mid = (a+b)/2;
if (a > b) return 0;
if (array[mid] == x) return 1;
else if (array[mid] < x) return ricerca_lineare(array, mid+1, b, x);
else return ricerca_lineare(array, a, mid-1, x);
}
1.
2.
3.
4.
5.
6.
7.
Esercizi su tail recursion
Scrivere una funzione ricorsiva che, data una lista di interi
positivi, restituisca il massimo intero nella lista. Implementare la
funzione con e senza tail recursion.
Scrivere una funzione ricorsiva che, data una lista di interi,
restituisca la loro somma. Utilizzare la tail recursion.
Scrivere una funzione ricorsiva che restituisce la media degli
elementi di una lista di interi positivi. Utilizzare la tail recursion.
Scrivere una funzione ricorsiva che stampi il contenuto di una pila.
Utilizzare la tail recursion.
Scrivere una funzione ricorsiva che converta una lista in una lista
circolare.
Scrivere una funzione ricorsiva che cerchi un elemento in una lista
circolare. Utilizzare la tail recursion.
Scrivere una funzione ricorsiva che conti il numero di elementi di
una lista circolare. Utilizzare la tail recursion.
NOTA: scrivere sempre pre e post condizione di ogni funzione
Esercizio 1
Scrivere una funzione ricorsiva che, data
una lista di interi positivi, restituisca il
massimo intero nella lista. Implementare
la funzione con e senza tail recursion.
Pre condizioni:
La funzione prende in ingresso una lista di
interi positivi
Post condizioni:
La funzione restituisce l’intero di massimo
valore nella lista e 0 se la lista è vuota
Implementazione ricorsiva
#define MAX(a, b) (a > b ? a : b)
int max(struct list *l)
{
if (l == NULL) return 0;
return MAX(l->el, max(l->next));
}
Implementazione ricorsiva con
tail recursion
int max(struct list *l, int mx)
{
if (l == NULL) return mx;
if (l->el > mx) mx = l->el;
return max(l->next, mx);
}
int max_tr(struct list *l)
{
return max(l, 0);
}
Esercizio 3
Scrivere una funzione ricorsiva che restituisce
la media degli elementi di una lista di interi
positivi. Utilizzare la tail recursion.
Pre condizioni:
la funzione prende in ingresso una lista di interi
positivi
Post condizioni:
La funzione restituisce la media (somma degli
elementi / numero degli elementi)
Svolgimento
int avg(struct list *l, int somma, int n)
{
if (l == NULL) return somma/n;
somma += l->el;
n++;
}
return avg(l->next, somma, n);
int avg_tr(struct list *l)
{
return avg(l, 0, 0);
}
Esercizio 4
Scrivere una funzione che stampi il
contenuto di una pila. Utilizzare la tail
recursion.
Pre condizioni:
la funzione prende in ingresso una pila
Post condizioni:
la funzione stampa la pila
Svolgimento
void stampa_pila(struct pila *p)
{
if (!pila_vuota(p))
{
printf("%d\n", pop(p));
stampa_pila(p);
}
}
Esercizio 5
Scrivere una funzione ricorsiva che
converta una lista in una lista circolare.
Pre condizioni:
la funzione prende in ingresso una lista
Post condizioni:
la funzione rende la lista circolare
(restituisce NULL se la lista è vuota)
Svolgimento
void rendi_circolare(struct list *l, struct list *s)
{
if (l->next == NULL) l->next = s;
else rendi_circolare(l->next, s);
}
void rendi_circolare_tr(struct list *l)
{
if (l == NULL) return NULL;
rendi_circolare(l, l);
}
Esercizio 6
Scrivere una funzione ricorsiva che cerchi
un elemento in una lista circolare.
Utilizzare la tail recursion.
Pre condizioni:
la funzione prende in ingresso una lista
circolare e un elemento
Post condizioni:
la funzione restituisce 1 se l’elemento è
stato trovato, 0 altrimenti.
Svolgimento
int ricerca(struct list *l, struct list *s, int x)
{
if (l->next == s) return l->el == x;
}
return l->el == x || ricerca(l->next, s, x);
int ricerca_tr(struct list *l, int x)
{
if (l == NULL) return 0;
return ricerca(l, l, x);
}
Esercizio bonus sulle pile
Scrivere una funzione che, dato un intero
positivo in base 10 e una base, restituisca una
stringa con la rappresentazione dell’intero nella
nuova base. Utilizzare le pile.
Pre condizioni:
la funzione prende in ingresso un intero positivo e
una base
Post condizioni:
la funzione alloca e restituisce una stringa
contenente la rappresentazione del numero nella
nuova base
Svolgimento
char *converti(unsigned int k, unsigned int b)
{
struct pila *p = crea_pila();
int conta = 0;
char *s, *rappr;
if (k == 0) { conta++; push(p, 0); }
while(k > 0)
{
push(p, k % b);
k /= b;
conta++;
}
rappr = s = (char *)malloc(conta+1);
while(!pila_vuota(p))
{
int digit = pop(p);
if (digit < 10) *s = '0'+digit;
else *s = 'A'+digit-10;
s++;
}
*s = 0;
}
return rappr;