Contraste entre Recursão e Iteração - Entendendo Diferenças e Aplicações

Esse artigo faz uma introdução breve a recursão e iteração com a intenção de contrastar suas diferenças e usos. Porém, para que esse requisito fosse atendido, diferentes linguagens foram empregadas. O propósito é justamente não se prender as linguagens, mas sim a lógica que é expressa em sua legítima forma de código. Ressalta, também, que por conta dos códigos o artigo se tornará um pouco mais extenso que o habitual mantido aqui no Autociência.

Representação surrealista da recursividade infinita
(Foto: ĐāżŦ {mostly absent} / CC BY-NC-ND)

É comum e do conhecimento de muitos a criação de algoritmos iterativos. E, dentro do estudo básico da programação, é comum também que livros apresentem o conceito de recursão logo após ensinarem iteração e funções. A iteração e recursão são técnicas que permitem que um bloco de instruções seja executado repetidamente, porém, ambas possuem abordagens diferentes.

Iteração

Segundo o dicionário Aurélio, iteração significa:

Iteração: sf. 1. Ato de iterar; repetição.

Um exemplo utilizando a linguagem C:

#include <stdio.h>

int main() {
    int i;

    for (i = 0; i <= 5; i++)
        printf("%d\n", i);
 
    return 0;
}

Esse programa imprime uma sequência numérica de 0 a 5 (inclusivamente) na base decimal. Ou seja, repete a mesma "instrução" seis vezes (contando com o zero). A palavra "instrução" está entre aspas porque, na verdade, printf é uma função que é convertida em várias instruções ao processador. Veja, abaixo, um exemplo com código equivalente em Assembly MIPS.

    .data
nl: .asciiz "\n"
    .text
main:
    add $t0, $zero, $zero
loop:
    li $v0, 1
    add $a0, $t0, $zero
    syscall

    li $v0, 4
    la $a0, nl
    syscall

    add $t0, $t0, 1

    ble $t0, 5, loop
    li $v0, 10
    syscall

Comentando o código acima, sem aprofundamento em baixo nível: um registrador $t0 recebe o valor zero. Depois, o registrador $v0 recebe o código de operação 1, que significa exibir um inteiro. Então, esse inteiro que está em $t0 é armazenado no registrador $a0. Quando syscall é acionado com o código de operação 1 em $v0, o inteiro contido em $a0 é lido e exibido. Depois, uma quebra de linha é exibida; $t0 é incrementado de 1 e existe um teste lógico (branch less or equal 5 - menor ou igual a 5) em que se o resultado for verdadeiro, retorna-se ao label loop e o programa executa esse ciclo de instruções novamente. Por fim, quando a condição não é mais verdadeira, o programa é finalizado passando o código 10 (exit) ao registrador $v0, assim quando a chamada de sistema (syscall) acontece, o programa é encerrado.

Um código realmente equivalente em Assembly — ao que foi escrito em C — pode ser obtido utilizando o argumento -S no compilador GCC, ao tentar compilar o código. Ex.: gcc -S source.c -o assembly.s.

Note como uma operação em alto nível pode se tornar várias em baixo nível, dependendo do número de endereços que a arquitetura do processador trabalha (comum três, dois ou um).

"Uma linguagem de alto nível expressa operações em uma forma algébrica concisa, usando variáveis. Uma linguagem de máquina expressa operações em uma forma básica envolvendo a movimentação de dados de e para os registradores" (STALLINGS, 2010).

O código em Assembly pode parecer um pouco confuso, já que primeiro é recuperado o operador ou operação (opcode) e depois os operandos. Mas o exemplo em C que foi exibido deixa esse código mais sugestivo. E se você não entendeu muito bem, não se preocupe. A saída de ambos os códigos será a seguinte:

0
1
2
3
4
5

Recursão

Recursão significa que uma sub-rotina (método, procedimento ou função) está chamando ela própria. A recursão pode ser finita ou infinita.

Existem muitos algoritmos que são recursivos porque a ideia de recursividade está ligada ao conceito de "dividir para conquistar". No livro Introduction to Algorithms os autores dizem (em tradução livre) que:

"Muitos algoritmos úteis são recursivos em estrutura: para resolver um certo problema, eles chamam eles próprios recursivamente uma ou mais vezes para lidarem com subproblemas intimamente relacionados" (CORMEN; LEISERSON; RIVEST; STEIN, 2009).

Um exemplo prático utilizando Python para cálculo fatorial:

#!/usr/bin/env python3

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

print("3! =", fat(3))

Por definição, o fatorial de 0 é 1. Então o código acima retornará 1 se o valor de n for igual a 0. Senão ele retornará n vezes o fatorial de n menos 1 até a primeira condição ser atendida.

Teste de Mesa
n	teste	retorno	resultado
3	3 == 0 (falso)	3 * fat(2)	3 * fat(2)
2	2 == 0 (falso)	2 * fat(1)	3 * fat(2) * fat(1)
1	1 == 0 (falso)	1 * fat(0)	3 * fat(2) * fat(1) * fat(0)
0	0 == 0 (verdadeiro)	1	3 * fat(2) * fat(1) * 1
1	1 == 0 (falso)	1 * 1	3 * fat(2) * 1 * 1
2	2 == 0 (falso)	2 * 1	3 * 2 * 1 * 1
3	3 == 0 (falso)	3 * 2	6

A mesma simulação também é válida para o fatorial de 4, que resulta em 24. Porém, o número de vezes em que essa função é chamada aumenta conforme o número que for passado também aumentar. Com fatorial de 3 a função foi chamada 4 vezes. Em outros casos a função pode ter mais de uma chamada recursiva, como no cálculo de Fibonacci. Saída:

3! = 6

A iteração em linguagens funcionais, como LISP, é geralmente substituída por recursão. Em Common Lisp encontramos duas funções importantes: car e cdr. A função car retorna o primeiro elemento de uma lista, enquanto que cdr retorna o restante. Com essas duas funções é possível verificar, recursivamente, se um dado elemento pertence a uma lista ou não. Exemplo:

(defun f (e lst)
  (if (null lst)
          nil
          (if (eql e (car lst))
                  t
                  (f e (cdr lst)))))

(format t "Elemento x na lista (a b d 5 x z): ~D~%" (f 'x '(a b d 5 x z)))

Lisp utiliza a notação prefixa, então isso significa que uma operação como $$5 + 2 \times 3 \div 10$$ (notação infixa) ficará (+ 5 (/ (* 2 3) 10)) (notação prefixa). Esse formato pode ser um pouco mais confuso ao ser humano, mas por outro lado facilita à máquina já que é assim que a mesma, em baixo nível, trabalha (segundo vimos em Assembly).

O código acima começa com a declaração de uma função f. Essa função recebe um elemento e uma lista. Caso a lista seja nula, ela retorna nil, que significa lista vazia e é equivalente ao false e null de outras linguagens. Caso a lista não esteja vazia, o programa compara o elemento e com o primeiro elemento da lista utilizando a função car. Se essa verificação for verdadeira, retorna t, que significa true. Caso contrário, retorna a chamada da própria função passando o mesmo elemento e o restante da lista, utilizando a função cdr.

Saída:

Elemento x na lista (a b d 5 x z): T

Devo usar Recursão ou Iteração?

Em todos os exemplos anteriores o uso da recursão e iteração são comutáveis. Isso significa que você pode usar tanto uma abordagem quanto outra para várias as situações. Então talvez surja a dúvida: devo usar recursão ou iteração?

A resposta mais sensata é: depende. A recursão permite solucionar muitos problemas, exigindo menos esforço de codificação e lógica, através da divisão do mesmo em pequenas partes. Solucionar alguns problemas através da iteração pode ser bem trabalhoso e demorado. Por outro lado — em termos de eficiência — a iteração é mais rápida em muitos casos, uma vez que em sua forma mais simples e genérica ela consiste na reexecução de um conjunto de instruções enquanto que cada chamada recursiva necessita da criação de uma nova sub-rotina em memória (que pode conter endereços de parâmetros e endereço de retorno).

Empilhamento em memória de procedimentos que são chamados.
(Fonte: William Stallings. Arquitetura e Organização de Computadores)

Pois, os valores dos parâmetros não podem ser perdidos e a recursão deve funcionar adequadamente para cada chamada como se fosse uma nova função totalmente a parte da que está em execução. Por isso uma pilha é utilizada em procedimentos reentrantes. Um procedimento reentrante, segundo William Stallings (2010), "é aquele em que é possível ter várias chamadas abertas ao mesmo tempo. Um procedimento recursivo (aquele que chama a si mesmo) é um exemplo do uso desse recurso".

Exemplos Utilizando Estruturas de Dados

Veja um exemplo com uma estrutura de dados do tipo árvore binária. Abaixo, é possível ver uma árvore binária com esses nós que são exibidos na imagem.

Estrutura do tipo árvore binária com 6 nós.

Essa árvore é composta por um nó do tipo Node que contém três atributos públicos: dado do tipo inteiro, referência para o próximo nó a esquerda e referência para o próximo nó a direita. Código em Java:

public class Node {
    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

Note que o encapsulamento foi omitido porque a intenção é simplificar com exemplos e não complicar.

A árvore possui um nó raiz, que é restrito apenas a ela. Quando essa árvore é criada, seus nós também são criados de acordo com a imagem anterior de referência.

public class Tree {
    private Node root;

    public Tree() {
        root             = new Node(5);
 
        root.left        = new Node(2);
        root.right       = new Node(8);

        root.left.right  = new Node(4);

        root.right.left  = new Node(7);
        root.right.right = new Node(9);
    }
}

Por algum motivo desejamos somar o valor de todos os elementos dessa árvore. Então surgem duas soluções: recursiva e iterativa.

Contabilização por Recursão

Por recursão o código fica bem mais legível e intuitivo, além de pequeno. É preciso criar dois métodos: o que retorna a soma e o que o chama.

private int sumNodes(Node node) {
    if (node == null) {
        return 0;
    } else {
        return node.data + sumNodes(node.left) + sumNodes(node.right);
    }
}

public int sum(int opc) {
    if (opc == 1) {
        return sumNodes(root);
    } else {
        return -1;
    }
}

Execução:


public class Main {
    public static void main(String[] args) {
        Tree tree = new Tree();

        int total = tree.sum(1);
        System.out.println("Total = " + total);
    }
}

Saída:

Total = 35

Contabilização por Iteração

Para contabilizar o total utilizando iteração é preciso criar uma estrutura de dados a parte (caso não queira utilizar recursos da linguagem em uso). Para esse caso serve uma fila encadeada (ou fila dinâmica). Essa fila armazena um elemento do tipo Element que contém os seguintes atributos públicos:

Node (dado)
Element (ele próprio, que aponta para o próximo elemento)

Código:

public class Element {
    public Node data;
    public Element next;

    public Element(Node data) {
        this.data = data;
        next = null;
    }
}

Esse elemento é manipulado por nossa fila dinâmica, que possui três métodos apenas: adiciona no fim, remove no começo e identifica se a fila está vazia.

public class Queue {
    private Element first;

    public void add(Node data) {
        if (first == null) {
            first = new Element(data);
        } else {
            Element newElement = new Element(data);
            Element aux = first;
            while (aux.next != null) {
                aux = aux.next;
            }
            aux.next = newElement;
        }
    }

    public Node remove() {
        Node data = null;

        if (!isEmpty()) {
            data = first.data;
            first = first.next;
        }
        return data;
    }

    public boolean isEmpty() {
        if (first == null) {
            return true;
        } else {
            return false;
        }
    }
}

Agora que temos nossa estrutura de dados auxiliar, resta-nos contabilizar os elementos da árvore iterativamente. Para isso, a lógica consiste em pegar cada nó e adicioná-los na fila (tanto o nó a esquerda quanto o nó a direita) de forma que um laço de repetição possa iterar sobre essa fila. Em paralelo, o valor dos nós é contabilizado.

private int sumNodes2() {
    int total = 0;
    Queue queue = new Queue();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node node = queue.remove();
        total = total + node.data;

        Node left = node.left;
        Node right = node.right;

        if (left != null) {
            queue.add(left);
        }
        if (right != null) {
            queue.add(right);
        }
    }

    return total;
}

Reforçando o que foi escrito no código acima:

Um contador é criado
Uma fila é criada
A fila recebe o nó raiz
Enquanto a fila não estiver vazia

Um nó é removido da fila e armazenado em uma variável
O valor desse nó é contabilizado
O nó esquerdo desse elemento é recuperado
O nó direito desse elemento é recuperado
Se o nó esquerdo não for nulo então ele é colocado na fila
Se o nó direito não for nulo então ele é colocado na fila
Retorna ao primeiro passo 4 descrito

Teste com as duas chamadas:

public class Main {
    public static void main(String[] args) {
        Tree tree = new Tree();

        int total1 = tree.sum(1);
        int total2 = tree.sum(2);
  
        System.out.println("Total (recursion) = " + total1);
        System.out.println("Total (iteration) = " + total2);
    }
}

O método sum() foi modificado para chamar a contagem por iteração quando recebe o valor 2. Saída:

Total (recursion) = 35
Total (iteration) = 35

Obs.: usando o método estático System.nanoTime() foi possível notar que a execução do método recursivo durou 22.737 ns enquanto que o iterativo durou 3.462.209 ns.

Esse é um bom exemplo de quando não utilizar iteração. Há algoritmos de ordenação de dados, inteligência artificial e ainda outros que não compensa abordá-los iterativamente a não ser por recursão. E da mesma forma existe o oposto em alguns outros algoritmos como no cálculo de Fibonacci onde é melhor evitar a recursão ou isso pode gerar um estouro de memória stack (famoso stack overflow, que significa que a pilha que foi mencionada para armazenamento de procedimentos atingiu o seu limite). A recursão e a iteração ainda podem ser combinadas como uma forma de percorrer diretórios em um sistema de arquivos ou serem usadas para construir algoritmos para encontrar melhores caminhos, como no caso do Minimax aplicado em jogo da velha e xadrez.

O que você aprendeu

Você acompanhou o artigo propedêutico de uma série sobre recursividade, que aos poucos será publicada. Viu exemplos de uso em diversas linguagens, quando utilizar e principalmente quando evitar. Você aprendeu, especificamente:

O que é iteração.
O que é recursão.
A aplicação de recursão e iteração.
Quando utilizar abordagens recursivas ou iterativas (alguns casos).
Quando não utilizar abordagens recursivas ou iterativas (alguns casos).

Por fim, é importante ressaltar que há regras e exceções; há, também, maneiras diferentes de implementar um código assim como interpretá-lo (humanamente falando). Portanto, se você leu esse artigo e tem uma abordagem diferente do que foi apresentado ou alguma crítica/sugestão, não hesite em deixar nos comentários.

Referência Bibliográfica

CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introduction to Algorithms. 3 ed. Cambridge: The MIT Press, 2009.

FERREIRA, A. B. H. Miniaurélio Século XXI Escolar: O minidicionário da língua portuguesa / Aurélio Buarque de Holanda Ferreira. 4. ed. rev. Ampliada – Rio de Janeiro: Nova Fronteira, 2000.

GRAHAM, P. ANSI common lisp. Nova Jérsei: Prentice Hall, 1996.

GNU. car & cdr - Programming in Emacs Lisp. Disponível em <https://www.gnu.org/software/emacs/manual/html_node/eintr/car-_0026-cdr.html>. Acesso em 17 jul. 2018.

MISSOURI STATE UNIVERSITY. MIPS syscall functions available in MARS. Disponível em <https://courses.missouristate.edu/KenVollmar/mars/Help/SyscallHelp.html>. Acesso em 20 jul. 2018.

STALLINGS, W. Arquitetura e Organização de Computadores. 8. ed. São Paulo: Prentice Hall, 2010.

WIKIBOOKS. Assembly/Instruction Formats. Disponível em <https://en.wikibooks.org/wiki/MIPS_Assembly/Instruction_Formats#Opcodes>. Acesso em 20 jul. 2018.

Para citar esse artigo:

Autociência

Pesquisar este blog