Logica Algoritmo 08 Recursividade

Lógica de
Programação
Recursividade

Regis Pires Magalhães [e-mail] Última atualização em 07/08/2008

Recursividade
• Um algoritmo que para resolver um problema divide-o em subprogramas mais simples, cujas soluções requerem a aplicação dele mesmo, é chamado recursivo, seja de forma direta ou indireta. • Em geral, uma rotina recursiva R pode ser expressa como uma composição formada por um conjunto de comandos C (que não contém chamadas a R) e uma chamada (recursiva) à rotina R:
Recursão
Direta

Exemplo
• Fatorial
– A definição de fatorial é:
• F(n) = 1 se n = 0 ou n = 1;
• F(n) = n * F(n-1), se n>1.
• onde n é um numero inteiro positivo. Uma propriedade
(facilmente verificável) dos fatoriais é que:
– n! = n * (n-1)!

– Esta propriedade é chamada de propriedade recursiva: o fatorial de um numero pode ser calculado através do fatorial de seu antecessor.
•
•
•
•
•

F(4) = 4 * F(4-1)
F(3) = 3 * F(3-1)
F(2) = 2 * F(2-1)
F(1) = 1 * F(1-1)
F(0) = 1

Caso base ou Condição de Parada
Como uma função recursiva pode chamar a si mesma indefinidamente, é essencial a existência do caso base, ou condição de parada.

Forma geral
• Esquematicamente, os algoritmos recursivos têm a seguinte forma: se "condicao para o caso de base" entao resolucao direta para o caso de base senao uma ou mais chamadas recursivas fimse Caso Base
• Um algoritmo recursivo pode ter um ou mais casos de base e um ou mais casos gerais.
• E para que o algoritmo termine, as chamadas recursivas devem convergir em direção ao caso de base, senão o algoritmo não terminará jamais.
• Convergir significa ter uma parte menor do problema para ser resolvido.
F(4) = 4.F(4-1)
F(3) = 3.F(3-1)
F(2) = 2.F(2-1)
F(1) = 1.F(1-1)
F(0) = 1 ------------ Caso Base
F(1) = 1.1
F(2) = 2.1
F(3) = 3.2
F(4) = 4.6

Exemplo algoritmo "fatorial" var numero: inteiro funcao fat (n:Inteiro):Inteiro inicio se n=0 entao retorne 1 senao retorne n * Fat (n-1) fimse fimfuncao inicio escreva("Digite um número: ") leia (numero)