[Recursividade, parte 1] Introdução

"To understand recursion, we first need to understand recursion." - Anonymous

Entender recursividade é algo fundamental para qualquer bom programador, pois diversas estruturas na computação são naturalmente recursivas, como exemplo, podemos citar a estrutura de diretórios em um sistema operacional.

Uma definição recursiva é mais que um simples trecho de código, é uma forma enxuta e eficiente de definir processos computacionais e expressar ideias. Mas o que vem a ser um procedimento recursivo?

Definição: "Um procedimento recursivo, é todo procedimento definido em termos dele mesmo".

Recursão é uma técnica muito poderosa em definições matemáticas. Como exemplo, podemos citar a função fatorial:

                                                                    F(0) = 1

                                                                    F(n) = n * F(n-1)

A definição acima mostra que para encontrarmos o fatorial de n, precisamos encontrar o fatorial de n-1, e para encontrar o fatorial de n-1, precisamos encontrar o fatorial de n-2, e assim sucessivamente, até alcançarmos o caso base F(0). Fazendo n = 5, temos:

                              F(5) = 5 * F(4)

                                               F(4) = 4 * F(3)

                                                                F(3) = 3 * F(2)

                                                                                 F(2) = 2 * F(1)

                                                                                                  F(1) = 1 * F(0)

                                                                                                                   F(0) = 1

Podemos perceber que em cada etapa precisamos da solução para um problema de tamanho menor.

Agora, vamos apresentar algumas implementações recursivas da função fatorial.

Implementação em Haskell

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial n-1

Implementação em C

#include <stdio.h>
#include <stdlib.h>

int factorial(int n) {
  if(n == 0)
    return 1;
  else
    return n * factorial(n-1);
}

int main() {
  int n;
  scanf("%i", &n);
  printf("%i", factorial(n));
  return 0;
}

Após essa explanação, é importante deixar claro que recursividade não serve apenas para calcular fatorial, que foi abordado nesse post inicial por ser um exemplo simples. No entanto, existem aplicações muito mais interessantes que abordaremos nos posts seguintes.