Algoritmos recursivos

Algoritmos recursivos são aqueles que resolvem um problema dividindo-o em subproblemas menores do mesmo tipo.

Cada subproblema é resolvido da mesma forma que o problema original até que o problema seja pequeno o suficiente para ser resolvido de forma direta. Em seguida, as soluções dos subproblemas são combinadas para resolver o problema original.

🎬 Vídeo

Características

  • Chamada Recursiva: O algoritmo chama a si mesmo com argumentos diferentes.
  • Condição de Parada: Há uma condição que termina a recursão, geralmente chamada de caso base.

Exemplos clássicos

Fibonacci

O problema de Fibonacci consiste em encontrar o n-ésimo número na sequência de Fibonacci, onde cada número é a soma dos dois números anteriores.

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) // Caso base
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2); // Chamada recursiva
}

int main() {
    int n = 5; 
    printf("O %dº número de Fibonacci é %d\n", n, fibonacci(n));
    return 0;
}

Neste exemplo, fibonacci(n) retorna o n-ésimo número de Fibonacci. Observe que:

  • quando n<=1, o caso base é alcançado e o valor de n é retornado;
  • caso contrário, o valor é calculado recursivamente somando os resultados das chamadas fibonacci(n - 1) e fibonacci(n - 2).

Como exemplo, a implementação iterativa seria:

int fib(int n) {
  int ant, pen = 0, atual = 1;

  if((n == 0) || (n == 1)) {
       return n;
  }
  
  for(int i = 2; i <= n; i++) {
    ant = pen;
    pen = atual;
    atual = ant + pen;
  }
  return atual;
}

Fatorial

O problema de fatorial consiste em encontrar o fatorial de um número, que é o produto de todos os números inteiros positivos de 1 até o número dado.

#include <stdio.h>

int fatorial(int n) {
    if (n == 0) // Caso base
        return 1;
    else
        return n * fatorial(n - 1); // Chamada recursiva
}

int main() {
    int n = 5;
    printf("O fatorial de %d é %d\n", n, fatorial(n));
    return 0;
}

Neste exemplo, fatorial(n) retorna o fatorial de n. Quando n==0, o caso base é alcançado e 1 é retornado. Caso contrário, o fatorial é calculado multiplicando n pelo fatorial de n - 1.

Esses exemplos ilustram como os algoritmos recursivos funcionam, dividindo problemas maiores em subproblemas menores até atingir um caso base e, em seguida, combinando as soluções dos subproblemas para obter a solução do problema original.

Nesta página