Algoritimos Recursivos

ALGORITMOS RECURSIVOS

1. DESENVOLVIMENTO
Na ciência da computação, recursividade é a definição de uma subrotina tem a capacidade de se inovar a si mesmo. Recursividade pode ter como aplicação nos analisadores sintáticos recursivos para linguagens de programação. A grande vantagem da recursão está na possibilidade de usar um programa de computador finito para definir, analisar ou produzir um estoque potencialmente infinito de sentenças, designs ou outros dados. Vejamos:
Segundo Judith “Uma definição na qual o item que está sendo definido aparece como parte da definição é chamada definição indutiva ou definição recursiva. À primeira vista isto pode parecer sem sentido—como algo pode ser definido em termos dele próprio? Este procedimento funciona porque as definições recursivas são compostas de duas partes:
1.uma base, onde alguns casos simples do item que está sendo definido são dados explicitamente, e
2.um passo indutivo ou recursivo, onde outros casos do item que está sendo definido são dados em termos dos casos anteriores. (JUDITH, 1995, p.67).

A parte 1 nos fornece um ponto de partida na medida em que trata alguns casos simples; enquanto a parte 2 nos permite construir novos casos a partir desses casos simples, para então construir outros casos a partir desses novos, e assim por diante. (A analogia com demonstrações por indução matemática justifica o nome" definição indutiva". Em uma demonstração por indução, existe a base da indução, isto é, a demonstração de P(1)— ou a demonstração de P para algum outro valor inicial— e existe a hipótese indutiva, onde a validade de P(k+1) é deduzida da validade de P para valores menores.)
A recursão é uma ideia importante que pode ser utilizada para definir sequências de objetos, coleções mais gerais de objetos e operações sobre objetos. (O Predicado Prologna-cadeia-alimentar da Seção 1.5 foi definido recursivamente.) Até mesmo algoritmos podem ser definidos recursivamente.
2. EXEMPLOS
Esta função é um dos