Mostrar código-fonte de Recursividade (ciência da computação)

{{Sem-fontes|data=outubro de 2016}}
Em [[ciência da computação]], a '''recursividade''' é a definição de uma [[sub-rotina]] (função ou método) que pode invocar a si mesma. Um exemplo de aplicação da [[recursividade]] pode ser encontrado nos [[Analisador sintático descendente recursivo|analisadores sintáticos recursivos]] para [[Linguagem de programação|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.

== 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 [[algoritmo]]s importantes, bem como um elemento fundamental do paradigma de [[programação dinâmica]].

Praticamente todas as [[linguagem de programação|linguagens de programação]] usadas hoje em dia permitem a especificação direta de [[Sub-rotina|funções]] e procedimentos recursivos. Quando uma função é invocada, o computador (na maioria das linguagens sobre a maior parte das arquiteturas baseadas em [[LIFO|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 <code>for</code>, <code>while</code> ou <code>repeat</code>. Tais linguagens geralmente fazem uma [[recursão em cauda]] tão eficiente quanto a iteração, deixando os [[programador]]es exprimirem outras estruturas de repetição (tais como o <code>map</code> e o <code>for</code> 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 <math>\mu</math>-recursivas e as [[Máquina de Turing|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 [[Número natural|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:

<pre>
função fatorial(x: inteiro): inteiro
inicio
   se x = 0 então
      fatorial <- 1
   senão
      fatorial <- x * fatorial(x - 1)
   fim_se
fim
</pre>

Aqui está a mesma função codificada sem recursão. É importante mencionar que esta solução iterativa requer duas [[Variável (programação)|variáveis]] temporárias; em geral, formulações recursivas de algoritmos são frequentemente consideradas "mais enxutas" ou "mais elegantes" do que formulações iterativas.

<pre>
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
</pre>

=== 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 (computador)|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 [[Axiomas de Peano|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 <math>sucessor(n)</math> definimos o comportamento da função recursiva a partir de seu comportamento com entrada <math>n</math>). 

O exemplo clássico de uma função definida recursivamente é a seguinte definição da função <math>fatorial(n)</math>:

<math> fatorial(n) =
 \begin{cases}
 1 & \mbox{se } n = 0 \\
 n \times fatorial(n-1) & \mbox{se } n > 0 \\
 \end{cases}
</math>

A partir desta definição, também chamada [[relação de recorrência]], calculamos <math>fatorial(3)</math> da seguinte forma:

<math>
  fatorial (3) = 3 * fatorial (3 - 1)
</math>
<math>
  = 3 * fatorial (2)
</math>
<math>
  = 3 * 2 * fatorial (2 - 1)
</math>
<math>
  = 3 * 2 * fatorial (1) 
 </math>
<math>
 = 3 * 2 * 1 * fatorial (1 - 1) </math>
<math>
  = 3 * 2 * 1 * fatorial (0)
 </math>
<math>
   = 3 * 2 * 1 * 1
</math>
<math>
  = 6
</math>

== 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:

<pre>
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
</pre>

Note que a função <code>fatorial</code> 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 <code>x</code> 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]] [[ímpar]]es em uma lista ligada:

<pre>
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 <- conta_impares(cabeca->proximo) + 1  /* recursão */
   senão
      conta_impares <- conta_impares(cabeca->proximo)  /* recursão em cauda */
fim
</pre>

Um bom [[compilador]] pode traduzir código recursivo em cauda para código iterativo. Com tal compilador, há vantagem em usar recursão em cauda para algumas funções. Definições recursivas algumas vezes são muito mais claras do que as iterativas. Contudo, chamadas recursivas são mais custosas do que iterações. Com recursão em cauda podemos ter código recursivo legível e uma implementação iterativa eficiente ao mesmo tempo.

O mais importante na recursão em cauda é que ao fazer uma chamada da função recursiva, os valores de retorno dela não necessitam ser conservados na pilha de chamada; quando a chamada recursiva retorna, ela vai diretamente para a posição de retorno previamente registrada. Assim, os compiladores que dão suporte à recursão em cauda economizam espaço e tempo.

== Recursão indireta ==
Funções podem ser recursivas (invocar a si próprias) indiretamente, fazendo isto através de outras funções: assim, "P" pode chamar "Q" que chama "R" e assim por diante, até que "P" seja novamente invocada.

Um exemplo é a [[Análise sintática (computação)|análise de expressões]]. Suponha que você tem um analisador sintático para cada tipo de sub-expressão, e tenha uma expressão "3 + (2 * (4 + 4))". A função que processa expressões "+" chamaria uma segunda função que processaria expressões "*", que, por sua vez, chamaria novamente a primeira.

== Recursão aninhada ==
Uma chamada recursiva pode receber um argumento que inclui uma outra chamada recursiva. Um exemplo é a [[função de Ackermann]], uma função que cresce de forma incrivelmente rápida.

<pre>
função ack(n: inteiro, m: inteiro): inteiro
inicio
   se n = 0 então
      ack <- m + 1
   senão se n > 0 E m = 0  então
      ack <- ack(n - 1, m)
   senão
      ack <- ack(n - 1, ack(n, m - 1))
   fim_se
fim
</pre>

Este é um exemplo de uma função que é muito mais fácil de escrever recursivamente: foi demonstrado que não existem definições equivalentes usando operadores aritméticos. Infelizmente uma computação recursiva direta desta função não é nem mesmo O(2n) em tempo ou espaço. 

A recursão aninhada é um tipo especial de recursão dupla, onde uma definição recursiva refere-se a si própria mais de uma vez.

== Ordem de chamada de funções ==
A ordem da chamada das funções podem mudar completamente a execução da função, veja o exemplo em [[C (linguagem de programação)|C]]:

=== Função 1 ===
<syntaxhighlight lang="C">
void recursiveFunction(int num)
{
   if (num < 5)
   {
      printf("%d\n", num);           
      recursiveFunction(num + 1);           
   }
}
</syntaxhighlight>

[[Ficheiro:RecursiveFunction1 execution.png]]

=== Função 2 com linhas trocadas ===
<syntaxhighlight lang="C">
void recursiveFunction(int num)
{
   if (num < 5)
   {
      recursiveFunction(num + 1);
      printf("%d\n", num);
   }
}
</syntaxhighlight>

[[Ficheiro:RecursiveFunction2 execution.png]]

== Função que retorna a soma dos números de n até 0 ==
<syntaxhighlight lang="C">
int soma(int n)
{
   if (n > 0)
      return n + soma(n - 1);
   else
      return 0;
}
</syntaxhighlight>

== Divisão de números com recursão ==
Função para dividir números utilizando somente soma e subtração:

<pre>
Função divisaoRec(inteiro num, inteiro den) retorna Inteiro
Inicio
   Se (num < den)
   Então
      Função_Retorna(0)
   Senão
      Função_Retorna(divisaoRec(num-den, den) + 1)
   Fim_Se
Fim
</pre>

== Usando vetores ==
Funções recursivas também podem ser usadas para acessar elementos de vetores, no exemplo abaixo é mostrado uma função recursiva que retorna a soma dos elementos de um vetor.

<syntaxhighlight lang="C">
int somatoria(int vetor[], int tamanho)
{
   if (tamanho > 0)
      return vetor[tamanho - 1] + somatoria(vetor, tamanho - 1);
   else
      return 0;
}
</syntaxhighlight>

== Ver também ==
* [[Recursividade]]

== Ligações externas ==
* [http://webmasters.tol.pro.br/portal/index.php?option=com_remository&Itemid=32&func=fileinfo&parent=category&filecatid=443 Introdução a Ciência da Computação - Scheme - PUC/RIO]
* [http://www.dcc.ufla.br/~bruno/aulas/lp2/recursao.html Recursão - UFLA - Lavras/MG]
* [http://www.dca.fee.unicamp.br/courses/EA072/lisp9596/node17.html Funções Recursivas - UNICAMP]
* [http://www2.fundao.pro.br/articles.asp?cod=33 Fundão da Computação - Recursão - definição e tipos mais utilizados]

[[Categoria:Estruturas de controle]]
[[Categoria:Lógica]]