Recursividade

Introdução

Para resolução de algum problema dentro da programação, às vezes é necessário dividi-lo em subproblemas do mesmo tipo. Isso pode ser feito com recursividade, que consiste em uma função chamar a si própria em tempo de execução. Quais os tipos de funções recursivas? Como funciona uma função recursiva?

Pilha de chamadas de função

Uma pilha de chamadas (callstack) de função representa a ordem de execução das funções de um programa. Tal ordem é resolvida partindo da última função adicionada na pilha. Dessa forma, a última função chamada é a primeira a ser resolvida, e assim sucessivamente. 

A pilha de chamadas é dinâmica e montada durante a execução.  

Definição de função recursiva

Uma função recursiva é uma função que chama a si própria direta ou indiretamente para resolver determinado problema. 

• Diretamente: a linha que indica a chamada da mesma função está dentro da própria função.
• Indiretamente: a função chama outra função (que pode chamar outra), e no fim acaba chamando a função original novamente.

A função recursiva parte seu funcionamento de um caso base. O caso base é a única parte da função que tem um retorno explícito no código e é responsável por resolver os passos recursivos acima dele na pilha de execução.

É obrigatória a existência de um caso base em uma função recursiva, pois a resolução dos demais casos é feita somente após o retorno do caso base.

O caso geral ou passo recursivo é a parte que a chamada da função é repetida, sendo adicionada à pilha de chamadas, mas com um parâmetro diferente do original.

É necessário que os passos recursivos sejam parecidos e menores que o problema principal.

O passo recursivo é executado até que se chegue ao caso base.

A cada resolução de um passo recursivo, obtém-se a resolução da função que está acima na pilha de chamadas, indo assim até o topo, que é o problema original.

Função recursiva para representar problema de Fibonacci (Linguagem C) 

Fibonacci é uma sequência definida de forma recursiva dada pela fórmula: Fn = F(n-1) + F(n-2).

Ou seja, um número dentro dessa sucessão é o resultado da soma de seus dois anteriores.

Os valores iniciais da sequência são 0 e 1 (casos base).

Um exemplo de implementação desse problema de forma recursiva é:

É possível observar que existem casos em que o retorno é explícito (casos-base). Esses retornos dão origem à resoluções que por fim resolvem ao problema final.

Entretanto, no problema de Fibonacci, à medida que se extende a pilha de chamadas, pode haver uma sobrecarga no processamento dessa grande quantidade de valores massivos oriundos dos passos recursivos. A seguinte imagem retrata esse cenário:

Conclusão

A princípio, a compreensão dessa funcionalidade pode ser complicada, porém as funções recursivas são fáceis, aleḿ disso fornecem soluções elegantes e bastante interessantes para alguns tipos de problema. Contudo, seu uso é desencorajado pelo principal motivo de que para cada chamada é necessário armazenar o estado da chamada anterior até que o caso particular ocorra, fazendo com que haja gasto excessivo de memória. Nesse sentido, na maioria dos casos é recomendável que se use iteração no lugar de recursão.