RECURSÃO II

Lista Ligada Revista

Algoritmos recursivos são especialmente úteis em algumas listas ligadas. Porém sua utilidade será vista com outra estrutura dinâmica: a árvore.

Por exemplo, como você imprimiria na tela os elementos de uma lista ligada simples? Um algoritmo poderia ser:

	Se a lista não estiver vazia:
		imprime o primeiro elemento
		imprime o resto da lista
		

Ou seja, a função seria algo como:

#define lista struct s_lista
struct s_lista {
	float valor;
	lista *prox;
};


/*
	Imprime a lista ligada na tela.

	Param:
		cabeca - a cabeça da lista
*/
void imprime(lista *cabeca) {
	/* vejo se a lista não está vazia */
	if (cabeca) {
		/* imprimo o primeiro elemento */
		printf("%f\n", cabeca->valor);

		/* imprimo o resto */
		imprime(cabeca->prox);
	}
}
		

Compare com nossa versão não recursiva:

void imprimeL(lista *cab) {
	lista *p; /* auxiliar */

	/* aponto p para o início da lista */
	p = cab;

	/* imprimo cada elemento da lista */
	while (p) {
		printf("nota: %f\n",p->valor);
		p = p->prox;
	}
}
		

Até aí sem muita diferença. Mas, e como você imprimiria a lista ao contrário? Opa! Agora o caso mudou... note que nossa lista ligada só tem ponteiros para frente... como faríamos para imprimir, então, a lista ao contrário?

Um algoritmo não recursivo exigiria uma lista auxiliar (na verdade, uma pilha), para onde copiaríamos a lista original. O truque está em, ao copiarmos cada elemento da lista original, em vez de inserirmos ele ao final da nova lista, inserimos no começo. Assim a nova lista será a original invertida.

Mas que trampo isso! E recursivamente, como faríamos? Um algoritmo poderia ser:

	Se a lista não estiver vazia:
		Se o elemento atual é o último elemento:
			imprime o elemento atual
		Senão:
			imprime o resto da lista
			imprime o elemento atual
		

Ou seja:

/*
	Imprime a lista ligada na tela, em ordem inversa.

	Param:
		cabeca - a cabeça da lista
*/
void imprimeInv(lista *cabeca) {
	/* vejo se a lista não está vazia */
	if (cabeca) {
		/* vejo se este é o último elemento */
		if (!cabeca->prox)
			printf("%f\n", cabeca->valor);
		else {
			/* imprimo o resto da lista em ordem inversa */
			imprimeInv(cabeca->prox);

			/* imprimo o elemento atual */
			printf("%f\n", cabeca->valor);
		}
	}
}
		

Nesse caso, o algoritmo recursivo simplificou muito nossa vida, podendo até ter proporcionado um ganho de memória, dependendo da estrutura da lista ligada.

Outro caso em que o algoritmo recursivo pode nos facilitar muito a vida é em buscas. Por exemplo, como você buscaria um elemento na lista? um algoritmo poderia ser:

	Se a lista estiver vazia:
		Não achou
	Senão:
		Se o elemento for o da cabeça:
			Achou
		Senão:
			Busca no resto da lista
		

Bastante simples, não? Uma possível implementação deste algoritmo é:

/*
	Verifica se um determinado valor está na lista. Retorna 0 se não e 1 se sim.

	Param:
		cabeca - a cabeca da lista
		valor - o valor buscado
*/
int busca(lista *cabeca, float valor) {
	/* Se a lista estiver vazia, não achou */
	if (!cabeca) return(0);

	/* vejo se o elemento é o da cabeça */
	if (cabeca->valor == valor) return(1);

	/* não achou ainda, busca no resto da lista */
	return (busca(cabeca->prox, valor));
}
		

Listas são um ambiente natural para recursão. Apesar disso, há que se ter sempre em mente que a recursão nunca é gratuita. Ela sempre vem às custas de tempo de execução (para, a cada chamada recursiva, empilhar uma cópia da função), e de memória (a cópia empilhada). Então recursão não deve ser usada como solução milagrosa. Porém, quando tempo de execução e recursos não são preocupações grandes, ela pode simplificar (e muito!) a implementação de certos algoritmos.