Algoritmos recursivos

ANÁLISE E DESENVOLVIMENTO DE SISTEMAS

LINGUAGEM DE PROGRAMAÇÃO
Algoritmos Recursivos

São Paulo
2013
ÍNDICE

1. INTRODUÇÃO 3
2. ALGORITMOS RECURSIVOS. 4
2.1 Torre de Hanói. 4
2.2 Quando aplicar recursão? 5
3. CONCLUSÃO. 6 1. INTRODUÇÃO

1.1 Fundamentos de Recursividades.

Um algoritmo que, para resolver um problema divide-o em subproblemas mais simples, cujas soluções requerem a aplicação dele mesmo, é chamado
Recursivo.
Cada vez que uma função é chamada de forma recursiva, é alojada e guardada uma cópia dos seus parâmetros de modo a não perder os valores dos parâmetros das chamadas anteriores. Em cada instância da função, só são diretamente acessíveis os parâmetros criados para esta instância, não sendo diretamente acessíveis os parâmetros de outras instâncias. A informação guardada na invocação de uma função é designada por Estrutura de Invocação e consiste basicamente na seguinte informação:

Endereço de retorno (quando a função terminar o programa deve continuar a sua execução na linha seguinte à invocação da função);
Estado dos registros e flags da CPU;
Variáveis passadas como argumentos para a função (por valor, referência, etc.);
Variável de retorno (por valor, referência, etc.);

A invocação de uma função recursiva é igual à invocação de uma função não recursiva, na qual é necessário guardar uma estrutura de invocação, sendo esta estrutura liberada depois do fim da execução da função e alteração/atualização do valor de retorno.

1.2 Solução de problemas.

A recursão é uma técnica que define um problema em termos de uma ou mais versões menores deste mesmo problema. Esta ferramenta pode ser utilizada sempre que for possível expressar a solução de um problema em função do próprio problema.

2. ALGORITMOS RECURSIVOS.

Qualquer função em linguagem C/C++ pode ser chamada de um modo recursivo, isto é, uma função pode chamar-se a