Repetição via Recursão

Quando o meio de abstração para procedimentos consiste quase unicamente em definir, nomear e invocar funções, utilizamos recursão para construir processos iterativos (enquanto que em outras linguagens teríamos laços como while e for).

Recursão Linear

Vejamos o exemplo clássico da função recursiva que calcula o fatorial de um número:

(define (fac n)
  (if (= n 0) 1
      (* n (fac (- n 1)))))

Como o procedimento fac é unidirecional e não gera efeitos colaterais - uma função pura - podemos computar o processo recursivo através de um modelo simples: basta substituir a definição de fac sempre que encontrarmos uma chamada, trocando também o argumento formal n no esqueleto do procedimento pelo valor passado na evocação. No exemplo abaixo já foi tomado o branch correto na expressão condicional.

         (fac 4)
      (* 4 (fac 3))
    (* 4 (* 3 (fac 2)))
  (* 4 (* 3 (* 2 (fac 1))))
(* 4 (* 3 (* 2 (* 1 (fac 0)))))
  (* 4 (* 3 (* 2 (* 1 1))))
    (* 4 (* 3 (* 2 1)))
      (* 4 (* 3 2))
        (* 4 6)
          24

Destaca-se que a computação deve armazenar no contexto do corpo da função fac a associação do valor da variável n. Isso acontece pois a multiplicação em (* n (fac (- n 1))) é avaliada somente após o retorno da chamada recursiva.

Assim, o processo transcorre tanto em tempo linear (altura da árvore) como em espaço linear (tamanho da pilha de chamadas) em relação à entrada n.

Recursão Iterativa: Tail-Recursion

Um outro exemplo de procedimento recursivo é o algoritmo de Euclides:

(define (gcd a b)
  (if (= b 0) a
      (gcd b (modulo a b))))

Compare o processo gerado com o anterior.

(gcd 1071 462)
(gcd 462 147)
(gcd 147 21)
(gcd 21 0)
21

Perceba que no caso do gcd, a computação não exige o armazenamento do contexto antes das chamadas recursivas: toda a informação necessária encontra-se nos argumentos da função.

Ambos os procedimentos denotam recursões lineares, ou seja, onde a invocação da função ocorre uma única vez durante a sua avaliação. Entretanto, enquanto fac toma uma quantidade de memória proporcional ao argumento de entrada, o processo descrito por gcd exige espaço constante e portanto constitui ainda uma iteração linear.

O que diferencia os dois procedimentos é o fato de que a última expressão no corpo de gcd é a invocação de uma função. Quando isso acontece dizemos que a função possui uma tail-call (chamada de cauda ou terminal) e quando a função evocada é recursiva, dizemos que ela é tail-recursive. Esse fenômeno possibilida a aplicação da chamada Tail Call Optimization, que elimina a necessidade de ocupar espaço na pilha de execução do programa.

A especificação da linguagem Scheme exige que implementações sejam properly tail-recursive, o que significa que o número de execuções de funções em tail-calls sequenciais é ilimitado.

Recursão Não-Linear e Linearização

Outras classificações de recursão incluem recursão mútua (odd? e even? definidas anteriormente) e recursão múltipla - onde a função é invocada em seu próprio corpo mais de uma vez. Um exemplo famoso de recursão múltipla binária é a função que calcula os números da sequência de Fibonacci:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

A árvore de chamadas recursivas gerada é bem maior nesse caso:

                            (fib 4)
          (+ (fib 3)                     (fib 2))
    (+ (fib 2)     (fib 1) )       (+ (fib 1) (fib 0))
(+ (fib 1) (fib 0))    1                 1       0
      1       0
       (+ 1 0)         1              (+ 1       0)
              (+ 1 1)                        1
                            (+ 2 1)
                               3

Para estimar a complexidade do processo, observe que o número de vezes em que o caso base da recursão é atingido na execução de (fib n) é exatamente igual ao (n+1)ésimo número de Fibonacci. Isso significa que esse procedimento é calculado em tempo exponencial proporcional à \( \phi ^ {n+1} \), onde \(\phi\) é o número de ouro.

Um primeiro passo para otimizar a computação é expressar o procedimento em uma iteração linear:

(define (fibo n)
  (let iter ((n n) (prev 1) (curr 0))
    (if (= n 0) curr
        (iter (- n 1) curr (+ prev curr)))))

Compare o tempo de execução de fib e fibo para n = 45.
Aproveite para tentar transformar o procedimento fac em uma iteração linear.

Alguns processos lineares podem ser otimizados ainda mais se explorarmos alguma propriedade que permita realizar, de uma vez, uma certa operação equivalente a múltiplas iterações.

;; recursao O(2^(n-1)) para base 2
;; 2^n = 2 * 2^(n-1) = 2^(n-1) + 2^(n-1)
(define (2^ n)
  (cond ((= n 0) 1)
        ((= n 1) 2)
        (else (+ (2^ (- n 1))
                 (2^ (- n 1))))))

;; recursao O(n)
;; b^n = b * b^(n-1)
(define (^ b n)
  (if (= n 0) 1 (* b (^ b (- n 1)))))

;; iteracao O(n)
;; b^n = b * b^(n-1)
(define (^ b n)
  (let iter ((n n) (prod 1))
    (if (= n 0) prod
        (iter (- n 1) (* b prod)))))

;; recursao O(log2(n))
;; b^n = (b^(n/2))^2
(define (^ b n)
  (cond ((= n 0) 1)
        ((even? n) (square (^ b (halve n))))
        (else (* b (^ b (- n 1))))))

;; iteracao O(log2(n))
;; b^n = (b^2)^(n/2)
(define (^ b n)
  (define (iter b n prod)
    (cond ((= n 0) prod)
          ((even? n) (iter (square b) (halve n) prod))
          (else (iter b (- n 1) (* b prod)))))
  (if (< n 0)
      (iter (/ 1 b) (- n) 1)
      (iter b n 1)))

;; PS:
(define (halve x) (ash x -1))
(define (square x) (* x x))

Tente aplicar a mesma técnica para computar a multiplicação de dois inteiros b e n em tempo logarítmico. O procedimento resultante deve se assemelhar ao algoritmo de multiplicação egípcia/russa.