Recursividade (ciência da computação) – Wikipédia  a enciclopédia livre
7 pág.

Recursividade (ciência da computação) – Wikipédia a enciclopédia livre


DisciplinaAlgoritmos16.146 materiais202.834 seguidores
Pré-visualização2 páginas
Recursividade (ciência da computação)
Origem: Wikipédia, a enciclopédia livre.
Em ciência da computação, a recursividade é a definição de uma subrotina (função ou método) que pode
invocar a si mesma. Um exemplo de aplicação da recursividade pode ser encontrado 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.
Índice
1 Algoritmos recursivos
2 Programação recursiva
2.1 Recursão versus Iteração
3 Funções recursivas
4 Funções recursivas em cauda
5 Recursão Indireta
6 Recursão Aninhada
7 Ordem de chamada de funções
7.1 Função 1
7.2 Função 2 com linhas trocadas
8 Função que retorna a soma dos números de 0 até n
9 Divisão de números com Recursão
10 Usando vetores
11 Ver também
12 Ligações externas
Algoritmos recursivos
Um método comum de simplificação consiste em dividir um problema em subproblemas do mesmo tipo. Como
técnica de programação, isto se denomina divisão e conquista, e constitui a chave para o desenvolvimento de
muitos algoritmos importantes, bem como um elemento fundamental do paradigma de programação dinâmica.
Praticamente todas as linguagens de programação usadas hoje em dia permitem a especificação direta de
funções e procedimentos recursivos. Quando uma função é invocada, o computador (na maioria das linguagens
sobre a maior parte das arquiteturas baseadas em pilhas) ou a implementação da linguagem registra as várias
instâncias de uma função (em muitas arquiteturas, usa-se uma pilha de chamada, embora outros métodos
possam ser usados). Reciprocamente, toda função recursiva pode ser transformada em uma função iterativa
usando uma pilha.
Toda função que puder ser produzida por um computador pode ser escrita como função recursiva sem o uso
de iteração; reciprocamente, qualquer função recursiva pode ser descrita através de iterações sucessivas.
Um exemplo simples poderia ser o seguinte: se uma palavra desconhecida é vista em um livro, o leitor pode
tomar nota do número da página e colocar em uma pilha (que até então está vazia). O leitor pode consultar esta
nova palavra e, enquanto lê o texto, pode achar mais palavras desconhecidas e acrescentar no topo da pilha. O
número da página em que estas palavras ocorrem também são colocados no topo da pilha. Em algum momento
do texto, o leitor vai achar uma frase ou um parágrafo onde está a última palavra anotada e pelo contexto da
frase vai descobrir o seu significado. Então o leitor volta para a página anterior e continua lendo dali.
Paulatinamente, remove-se seqüencialmente cada anotação que está no topo da pilha. Finalmente, o leitor volta
para a sua leitura já sabendo o significado da(s) palavra(s) desconhecida(s). Isto é uma forma de recursão.
Algumas linguagens desenvolvidas para programação lógica e programação funcional permitem recursões como
única estrutura de repetição, ou seja, não podem usar laços tais como os produzidos por comandos como for,
while ou repeat. Tais linguagens geralmente fazem uma recursão em cauda tão eficiente quanto a iteração,
deixando os programadores exprimirem outras estruturas de repetição (tais como o map e o for do Scheme)
em termos de recursão.
A recursão está profundamente entranhada na Teoria da computação, uma vez que a equivalência teórica entre
as funções -recursivas e as máquinas de Turing está na base das idéias sobre a universalidade do computador
moderno.
Programação recursiva
Em geral, uma definição recursiva é definida por casos: um número limitado de casos base e um caso recursivo.
Os casos base são geralmente situações triviais e não envolvem recursão.
Um exemplo comum usando recursão é a função para calcular o fatorial de um natural N. Nesse caso, no caso
base o valor de 0! é 1. No caso recursivo, dado um N > 0, o valor de N! é calculado multiplicando por N o
valor de (N-1)!, e assim por diante, de tal forma que N! tem como valor N * (N-1) * (N-2) * ... * (N-N)!,
onde (N-N)! representa obviamente o caso base. Em termos recursivos:
função fatorial(x: inteiro): inteiro
inicio
 se x = 0 então
 fatorial <- 1
 senão
 fatorial <- x * fatorial(x - 1)
 fim_se
fim
Aqui está a mesma função codificada sem recursão. É importante mencionar que esta solução iterativa requer
duas variáveis temporárias; em geral, formulações recursivas de algoritmos são freqüentemente consideradas
&quot;mais enxutas&quot; ou &quot;mais elegantes&quot; do que formulações iterativas.
função fatorial(x: inteiro): inteiro
var i, aux: inteiro
inicio
 aux <- 1
 para i de 1 até x faça
 aux <- aux * i
 fim_para
 fatorial <- aux
fim
Recursão versus Iteração
No exemplo do fatorial, a implementação iterativa tende a ser ligeiramente mais rápida na prática do que a
implementação recursiva, uma vez que uma implementação recursiva precisa registrar o estado atual do
processamento de maneira que ela possa continuar de onde parou após a conclusão de cada nova execução
subordinada do procedimento recursivo. Esta ação consome tempo e memória. (Note que a implementação de
uma função fatorial para números naturais pequenos é mais rápida quando se usa uma tabela de busca.)
Existem outros tipos de problemas cujas soluções são inerentemente recursivas, já que elas precisam manter
registros de estados anteriores. Um exemplo é o percurso de uma árvore; outros exemplos incluem a função de
Ackermann e algoritmos de divisão e conquista, tais como o Quicksort. Todos estes algoritmos podem ser
implementados iterativamente com a ajuda de uma pilha, mas o uso de uma pilha, de certa forma, anula as
vantagens das soluções iterativas.
Outra possível motivação para se escolher um algoritmo iterativo ao invés de um algoritmo recursivo é que nas
linguagens de programação modernas o espaço disponível para o fluxo de controle é geralmente bem menor
que o espaço disponível no heap, e algoritmos recursivos tendem a necessitar de mais espaço na pilha do que
algoritmos iterativos.
Funções recursivas
Funções cujos domínios podem ser definidos recursivamente (tal como o domínio dos números naturais)
possuem frequentemente definições recursivas que seguem a definição recursiva do domínio (no caso dos
naturais, definimos o comportamento da função com entrada 0, e para cada entrada positiva 
definimos o comportamento da função recursiva a partir de seu comportamento com entrada ).
O exemplo clássico de uma função definida recursivamente é a seguinte definição da função :
A partir desta definição, também chamada relação de recorrência, calculamos da seguinte
forma:
Funções recursivas em cauda
As funções recursivas em cauda formam uma subclasse das funções recursivas, nas quais a chamada recursiva é
a última instrução a ser executada. Por exemplo, a função a seguir, para localizar um valor em uma lista ligada é
recursiva em cauda, por que a última coisa que ela faz é invocar a si mesma:
registro noh
 dado: inteiro
 *proximo: registro noh
fim_registro
*acha_valor(*cabeca: registro noh, valor: inteiro): registro noh
inicio
 se cabeca = NULO então
 acha_valor <- NULO
 senão se cabeça.dado = valor então
 acha_valor <- cabeca
 senão
 acha_valor <- acha_valor(cabeca.proximo, valor)
 fim_se
fim
Note que a função fatorial usada como exemplo na seção anterior não é recursiva em cauda, pois depois
que ela recebe o resultado da chamada recursiva, ela deve multiplicar o resultado por x antes de retornar para
o ponto em que ocorre a chamada. Funções com este tipo de comportamento são por vezes denominadas
crescentemente recursivas.
É importante recordar que uma única função pode ter ambos os comportamentos, como ocorre na seguinte
função que conta os inteiros ímpares em uma lista ligada:
função conta_impares(*cabeca: registro noh): inteiro
inicio
 se cabeca = NULO então
 conta_impares <- 0
 senão se (cabeca->dado MOD 2) = 1 então
 conta_impares