5-06-2002

Negli esercizi dedicati alle liste abbiamo introdotto le seguenti strutture.

struct _nodo {
	int dato;
	struct _nodo *next;
};

typedef struct _nodo *lista;
typedef struct _nodo *puntatore;



Data una lista lineare di interi, calcolare la somma degli elementi 
con iterazione, ricorsione, ricorsione di coda.

/*
	iterazione
*/

	int somma( lista l ) {
		int s = 0;
		puntatore i;

		i=l;
		while( i != NULL ) {
			s+=i->dato;
			i=i->next;
		}
		return s;
	}

/*
	ricorsione
	definizione: 	la somma è 0 se la lista è vuota
			altriment è il primo + la somma dei rimanenti 
*/

	int somma( lista l ){
		if( l==NULL ) return 0;
		return l->dato + somma( l->next );
	}

/*
	possiamo rendere più leggibile il programma introducendo le seguenti funzioni:
*/
	int primo( lista l ){		/*restituisce il primo dato */
		return l->dato;
	}

	lista rimanenti( lista l ){	/* restituisce la lista dei rimanenti  */
		return l->next;
	}

	int somma( lista l ) {
		if( l==NULL ) return 0;
		return primo(l) + somma( rimanenti(l) );
	}

/*
	ricorsione di coda
*/

	int somma( lista l, int s ) {
		if( l==NULL ) return s;
		return somma( l->next, l->dato+s );
	}

/*
	scritto con le funzioni introdotte prima:

*/

	int somma( lista l, int s ) {
		if( l==NULL ) return s;
		return somma( rimanenti(l), primo(l)+s );
	}