Tipos de Algoritmos

Antes de começar nosso estudo de algoritmo, precisamos entender alguns conceitos fundamentais sobre o tema. Cobriremos aqui dois desses conceitos: tipos de algoritmos, e tipos de estratégias de projeto de algoritmo.

Algoritmos Iterativos e Recursivos

Nesta seção classificaremos algoritmos em dois grupos: algoritmos recursivos, e algoritmos iterativos. É importante saber as distinções entre esses tipos de algoritmos, bem como os pontos fortes e fracos de cada um, pois frequentemente precisamos escolher quando implementar um algoritmo de forma iterativa ou de forma recursiva. Sabendo as nuances de cada tipo de algoritmo, poderemos escolher qual o melhor tipo a ser usado em cada situação.

Algoritmos (Procedimentos) Recursivos

Recursão é auto-referência. Muitos sistemas possuem a capacidade de representar ou de referir a eles mesmos. Quando isso acontece, o sistema se auto-referencia. Algoritmos recursivos são um tipo de sistema que refere a si próprio.

Recursão ocorre quando algo é definido em termos de si mesmo ou de suas variações.O conteúdo sobre recursão desta seção é inspirado nos excelentes livros do Douglas Hofstadter. Recursão envolve estruturas aninhadas. Por exemplo, podemos identificar recursão quando alguém escreve um livro sobre escrita, ou quando uma pessoa está assistindo a um filme que mostra outra pessoa assistindo a um filme, ou quando uma imagem contém uma cópia de dela prória (talvez em menor escala). Este último caso é mostrado na figura abaixo, criada por Paul Noth para o The New Yorker.

Imagens aninhadas. Exemplo de recursão.

Dissemos acima que recursão ocorre quando algo é definido em termos de si mesmo ou de suas variações, mas como definir algo recursivamente de forma útil e precisa? Se uma coisa é definida unicamente em termos de si própria, existe uma circularidade inerente que não nos permite concluir nada sobre o que está sendo definido. Um exemplo desse tipo de definição circular seria:

Definição (inútil): Um procedimento recursivo é um procedimento que usa recursão.

A definição acima é um exemplo de como não fazer uma definição recursiva. Ela define um procedimento recursivo valendo-se da própria palavra sendo definida (recursão). Se o leitor não souber o que é recursão, a definição não vale de nada. E se o leitor souber o que é recursão, a definição é desnecessária.

Um outro exemplo de definição recursiva formulada de forma errada (incompleta) é a definição abaixo:

Definição (incompleta): O fatorial de um número , denotado por , é calculado como a seguir:

A definição acima é incompleta porque não dos diz como calcular o fatorial de nenhum número específico. Se tentarmos aplicá-la ao cálculo do fatorial de algum número, nunca seremos capazes de parar. Continuaremos calculando indefinidamente.

Definições recursivas (quando propriamente formuladas) nunca definem algo unicamente em termos de si mesmas, mas sempre em termos de versões mais simples de si mesmas. Um exemplo disso é a definição matemática de fatorial, agora feita de modo correto.

Definição (correta): O fatorial de um número , denotado por , é calculado como a seguir:

Com a adição de mais uma regra, sabemos que, ao chegar no zero, conseguiremos calcular seu fatorial e poderemos usar o resultado no cálculo do fatorial dos demais números, até chegarmos ao fatorial do número desejado inicialmente. O procedimento não executará indefinidamente.

Ou se preferirmos seguir a definição recursiva dada anteriormente, teremos o cálculo abaixo:.

Neste momento, é importante observarmos algumas coisas sobre o cálculo de realizado acima:

Um benefício de conceitos recursivos é que, em geral, a implementação da definição do conceito em uma linguagem de programação é uma tarefa simples e direta. Por exemplo, veja abaixo a implementação do cálculo do fatorial de um número. Mesmo que você não entenda alguns detalhes do código (não se preocupe, você entenderá em breve), tente ver a correspondência entre a definição recursiva do fatorial de um número e a implementação recursiva desta definição.

def fat(n):
    # Caso base: O fatorial de 0 é 1.
    if n == 0:
      return 1
    
    # O fatorial (fat) de um número n é: n * fat(n - 1).
    return n * fat(n - 1)

No código acima, foi simples traduzir para uma linguagem de programação (Python, neste caso) as duas partes da definição recursiva do fatorial de um número. É possível ler o código e identificar facilmente o que ele está fazendo. Na maioria dos casos, se um algoritmo pode ser definido de forma recursiva, a implementação do algoritmo será direta (mas nem sempre simples).

Outra vantagem de algoritmos recursivos é que eles são, em geral, fáceis de serem lidos. A correspondência entre a definição e a implementação é óbvia. Por outro lado, como veremos em breve, algoritmos recursivos não são muito eficientes em alguns casos, pois pode ser que eles realizem grandes quantidades de trabalho repetido. Nosso próximo exemplo irá ilustrar melhor essa ineficiência.

Definiremos agora uma sequência matemática muito famosa chamada Sequência de Fibonacci. Nessa sequência, os dois termos iniciais são e , e cada termo subsequente é igual à soma dos dois termos anteriores. O cálculo do -ésimo termo da sequência de Fibonacci pode ser definido recursivamente da seguinte forma:

Definição: O -ésimo termo da sequência de Fibonacci, denotado por , pode ser calculado da seguinte forma:

A partir da definição acima, podemos implementar o cálculo do -ésimo termo da sequência assim:

def fib(n):
    # Caso base: cálculo dos dois primeiros termos.
    if n <= 0:
      return 0
    if n == 1:
      return 1

    # Cálculo do n-ésimo termo.
    return fib(n - 1) + fib(n - 2)

Novamente, note a correspondência direta entre a definição e sua implementação. Entretanto, a implementação acima é ineficiente porque ela faz uma grande quantidade de trabalho repetido. Para ilustrar isso, veja a figura abaixo, ilustrando o cálculo de fib(5), que mostra as muitas chamadas repetidas da função fib, que, por questões de espaço, escrevemos simplesmente como f.

Exemplo da execução da função fib(5).

A título de curiosidade, existem formas mais eficientes de implementarmos a função fib, sem usar recursão, e sem fazer chamadas desnecessárias. Veremos como fazer isso mais à frente no curso.

Lição Geral

Para usar recursão de forma correta, é necessário prestar atenção a dois componentes:

Algoritmos (Procedimentos) Iterativos

Explicamos anteriormente o algoritmo recursivo para o cálculo do fatorial de um número inteiro positivo. Entretanto, ao estudarmos a definição, vemos que o fatorial de um número inteiro positivo nada mais é do que o produto de todos os inteiros positivos menores ou iguais a . Por exemplo:

Comparando este exemplo com o exemplo do fatorial recursivo, vemos que a principal diferença entre o procedimento recursivo e o iterativo é que o procedimento iterativo contém instruções completas de como realizar uma tarefa, ao passo que o procedimento recursivo contém instruções de como realizar uma tarefa tendo como base instâncias menores da mesma tarefa. Um exemplo tornará esta explicaçao mais clara.

Relembrando, a definição recursiva do fatorial de um número é a seguinte:

Definição: O fatorial de um número , denotado por , é calculado como a seguir:

A definição iterativa do fatorial é um número é a seguinte:

Definição: O fatorial de um número , denotado por , é calculado como a seguir:

Como dissemos acima, o procedimento iterativo nos diz cada passo do cálculo do fatorial de um número, enquanto o procedimento recursivo nos diz como calcular o fatorial de um número baseado no fatorial de um número menor, (, neste caso).

Na prática, é muito fácil distinguir um algoritmo recursivo de um algoritmo iterativo. O algoritmo recursivo sempre terá uma chamada a si mesmo. O algoritmo iterativo nunca terá isso. Veja abaixo o algoritmo recursivo para o cálculo do fatorial de um número e o algoritmo iterativo logo em seguida e compare os dois.

def fatorial_recursivo(n):
    if n == 0:
      return 1
    else:
      return n * fatorial_recursivo(n - 1)

def fatorial_iterativo(n):
  fatorial = 1
  for i in range(1, n + 1):
    fatorial = fatorial * i
  return fatorial

No código acima, a chamada à função range(1, n + 1) gera uma lista de números no intervalo , ou seja, indo de até .

As noções de algoritmo recursivo e algoritmo iterativo, bem como as nuances de Python, ficarão mais claras ao longo do curso. Nosso objetivo aqui é simplesmente dar uma breve introdução a estes tópicos.

Até aqui, classificamos algoritmos em iterativos e recursivos. Na próxima seção mostraremos outra classificação de algoritmos, de acordo com a estratégia que eles usam para resolver um dado problema. Essas duas classificações são independentes uma da outra (no sentido de que elas podem co-existir).


Estratégias (Paradigmas)

Na seção anterior demos uma noção básica de algoritmos recursivos e iterativos e das diferenças entre eles. Nesta seção daremos uma breve noção das diferentes estratégias usadas na criação de algoritmos. Essas estratégias são formalmente conhecidas como paradigmas de projeto de algoritmo e teremos um capítulo inteiro dedicado a estudar cada uma delas em detalhes. Mas por agora, gostaríamos unicamente de introduzi-las, para que quando as mencionarmos ao longo do curso, ou para que quando você as ver em algum algoritmo, você possa reconhecê-las e apreciar as diferenças entre elas.

Divisão e Conquista

Algoritmos que empregam o paradigma de divisão e conquista partem de um problema e o dividem em sub-problemas menores e independentes entre si, até que os sub-problemas sejam pequenos o bastante para ser resolvidos diretamente. As soluções desses sub-problemas são combinadas para a obtenção da solução do problema original.

Talvez você tenha identificado alguma similaridade entre a descrição acima e a descrição de algoritmos recursivos. Essa similaridade existe e ela se deve ao fato de que a divisão de um problema em problemas menores no paradigma de divisão é conquista é feita, grande parte das vezes, por meio de chamadas recursivas.

Um exemplo de algoritmo que emprega o paradigma de divisão e conquista é o algoritmo de ordenação chamado Mergesort. Nesse algoritmo, dividimos uma lista de números em listas de tamanho menor, que são facilmente ordenadas, e depois combinamos as listas menores (já ordenadas) em uma única lista.

Recursão/Backtracking

Um algoritmo que usa backtracking é um algoritmo que tenta diferentes soluções até encontrar uma que seja a correta. Quando o algoritmo encontra uma solução que não é correta, ele volta atrás e tenta outra. Em geral, algoritmos que usam backtracking são algoritmos que precisam testar cada configuração possível. Parte da eficiência do algoritmo reside no fato de que, na maioria dos casos, cada configuração é testada uma única vez.

A vantagem de se usar backtracking em vez de testar todas as possíveis soluções (força bruta) é que a natureza incremental do backtracking, bem como a possibilidade de se concluir que várias soluções derivadas de uma solução ruim não irão funcionar, faz com que backtracking seja mais eficiente que força bruta, em geral. O nome backtracking aparece atrelado a recursão porque, grande parte das vezes, recursão é a ferramenta usada para se implementar backtracking.

Algoritmos Gulosos

Um algoritmo guloso é um algoritmo que opera em etapas. A cada etapa, o algoritmo toma decisões locais irrevogáveis, ou seja, ele faz um palpite de qual é a melhor decisão a se tomar e nunca repensa essa decisão. O algoritmo progride assim até chegar à solução do problema original.

Algoritmos gulosos são úteis em muitos cenários, mas é difícil se chegar a um algoritmo guloso que dá a solução ótima para um problema, e é mais difícil ainda provar que a solução obtida por um algoritmo guloso é de fato ótima.

Programação Dinâmica

Algoritmos de programação dinâmica dividem o problema original em sub-problemas, armazenam a solução desses sub-problemas em uma tabela de resultados conhecidos, e combinam a solução dos sub-problemas para obter a solução do problema original.

Tanto algoritmos de programação dinâmica quanto algoritmos de divisão e conquista dividem o problema original em sub-problemas e combinam a solução dos sub-problemas para obter a solução do problema original. Entretanto, no paradigma de programação dinâmica, os sub-problemas aparecem mais de uma vez, por isso criamos a tabela para armazenar as soluções deles. Assim, quando encontramos um sub-problema para o qual já sabemos a solução, simplesmente retornamos o resultado armazenado na tabela em vez de recomputar a solução do sub-problema.