[Aula 13] Recursividade

Fala pessoal!!

Hoje falaremos de Recursividade que é um recurso muito útil em determinadas situações e desconhecida por muitos desenvolvedores.
Por esse motivo, é muito importante que se dê atenção ao exercício e ao desafio. O desafio em particular, é muito fácil de achar pronto na Internet....mas qual a graça?

RECURSIVIDADE

A idéia básica de um algoritmo recursivo consiste em diminuir sucessivamente o problema em um problema menor ou mais simples, até que o tamanho ou a simplicidade do problema reduzido permita resolvê-lo de forma direta, sem recorrer a si mesmo.
Quando isso ocorre, diz que o algoritmo atingiu uma condição de parada, a qual deve estar presente em pelo menos um local dentro algoritmo. Sem esta condição o algoritmo não pára de chamar a si mesmo, até estourar a capacidade da pilha de execução, o que geralmente causa efeitos colaterais indesejados e até mesmo o término indesejável do programa.

Vamos trocar isso tudo em miúdos?
Uma função recursiva é aquela que chama a si mesma passando, para a próxima chamada, um problema menor. Sendo que essa chamada deve estar dentro de uma condição de parada, que normalmente testa se o problema já está pequeno o suficiente. Se não houver a condição de parada, uma função vai chamar a outra (ela mesma), que vai chamar outra vez, que vai chamar outra vez... infinitamente. A cada chamada, há um consumo de memória e se existirem muitas chamadas, a ponto de consumir toda a memória, haverá um erro que fará o seu sistema parar, geralmente.

Para todo algoritmo recursivo existe um outro correspondente iterativo (não recursivo), que executa a mesma tarefa. Implementar um algoritmo recursivo em uma linguagem de programação de alto nível como Pascal e C é simples e quase imediato, pois o seu código é praticamente transcrito para a sintaxe da linguagem. Por essa razão, os algoritmos recursivos possuem código mais claro (legível) e mais compacto do que os correspondentes iterativos.
Existem situações onde é difícil encontrar o algoritmo iterativo correspondente, como é o caso da Torre de Hanói.
Algoritmos recursivos são muito usados em pesquisas de diretórios, inteligência artificial e em muitas outras áreas.

Um exemplo de algoritmo que utiliza a recursividade:

INICIO
	n : inteiro;
	LEIA(n);
	ESCREVA(fatorial(n));
FIM

FUNCAO fatorial(n :inteiro) : inteiro
INICIO
	SE (n < 2) ENTÃO;
		RETORNAR n;
	FIM SE
	RETORNAR n * fatorial(n-1);
FIM FUNCAO

Vamos fazer uma simulação do uso do exemplo anterior para verificarmos o fatorial de 4, ou seja, 4! (! É o símbolo de fatorial).

fatorial(4) = 4 * fatorial(3)
fatorial(3) = 3 * fatorial(2)
fatorial(2) = 2 * fatorial(1)
fatorial(1) = 1

Ou seja,

fatorial(4) = 4 * (3 * (2 * 1))

Então,

fatorial(4) = 24

Perceba que quando a função fatorial(1) foi chamada, ela não a chamou novamente, pois a condição de parada (SE (n < 2) ENTÃO) foi satisfeita.
Perceba também que o problema foi diminuído progressivamente até atingir o ponto de parada.

VANTAGENS:

DESVANTAGENS:

Exercício
1. Partindo da matriz abaixo fazer um algoritmo recursivo que mostre o nome de todos os filhos (toda a árvore) de um determinado ID.
Considerações:
- Considere que o elemento que tenha ID_PAI = 0 seja o elemento raiz.
- Desconsidere os títulos da tabela que mostra a matriz. Eles só servem para auxiliar na interpretação do problema.
- O resultado esperado para a mostra dos filhos do elemento com ID = 1 é:

Grupo de Estudos
	Algoritmos
		Aulas
		Exercícios
		Desafios
	PHP
	ASP
		Aulas
		Exercícios

| ID | ID_PAI | NOME			 |
| 1  |	0   | Grupo de Estudos |
| 2  |	1   | Algoritmos	   |
| 3  |	2   | Aulas			|
| 4  |	2   | Exercícios	   |
| 5  |	2   | Desafios		 |
| 6  |	1   | PHP			  |
| 7  |	1   | ASP			  |
| 8  |	7   | Aulas			|
| 9  |	7   | Exercícios	   |

Desafio

1. Criar o algoritmo para a resolução do problema da torre de Hanói, conforme detalhes no link: http://forum.ievolut...?showtopic=8807