1.2 Procedimentos e os Processos que Eles Geram

O que é um bom programador? Um bom programador é definido por habilidades que vão além do conhecimento técnico básico (como operações e sintaxe). Os elementos essenciais são:

Capacidade de Visualizar Processos

Antecipar consequências: Saber prever como um procedimento ou linha de código afetará o fluxo do programa, a eficiência, a manutenção e o resultado.
Simulação mental: Entender como o processo gerado por um código se desenrola, passo a passo, incluindo estados intermediários e possíveis erros.

Experiência com Padrões e Estratégias

Conhecimento de "movimentos valiosos": Dominar padrões de projeto, algoritmos eficientes e boas práticas.
Abstração eficaz: Saber combinar operações primitivas em procedimentos úteis e reutilizáveis.

Planejamento Sintético e Raciocínio Lógico

Pensamento reverso: Trabalhar de trás para frente a partir do resultado desejado (como um fotógrafo planeja exposição).
Controle do processo: Garantir execução ordenada e confiável do programa.

Aprendizado Contínuo com a Prática

Experiência acumulada: Desenvolver intuição através da exposição a cenários complexos.
Adaptação: Ajustar estratégias conforme o contexto (como técnicas fotográficas).

1.2.1 Recursão Linear e Iteração

Processo Recursivo Linear:

Expansão (acúmulo de operações) seguida de contração (execução das operações).
Requer memória proporcional a n (crescimento linear), pois o interpretador rastreia a cadeia de operações pendentes.

Processo Iterativo Linear:

Usa variáveis de estado atualizadas iterativamente:
Mantém estado fixo, evoluindo em espaço constante (memória fixa), mesmo para grandes n.

Sintaxe recursiva (porém com chamadas de cauda) gera processo iterativo. Mantendo um espaço constante, pois o estado é totalmente descrito pelas variáveis a cada passo. Exemplos em outras linguagens: o for e o while. A recursão sintática (código que chama a si) não implica necessariamente um processo recursivo (com crescimento de memória). Um procedimento recursivo pode gerar um processo iterativo se for tail-recursive⁴ (recursão de cauda).

Exercício 1.9: Resposta

Processo Recursivo:


(+ 4 5)                         ;; Chamada do procedimento 1
(inc (+ 3 5))                   ;; Passo 1: inc é adiado
(inc (inc (+ 2 5)))             ;; Passo 2: incs acumulam
(inc (inc (inc (+ 1 5))))       ;; Passo 3
(inc (inc (inc (inc (+ 0 5))))) ;; Passo 4: caso-base (a=0)
(inc (inc (inc (inc 5))))       ;; Passo 5: contração começa
(inc (inc (inc 6)))             ;; Passo 6
(inc (inc 7))                   ;; Passo 7
(inc 8)                         ;; Passo 8
9                               ;; Resultado

Processo Interativo:


(+ 4 5) ;; Chamada do procedimento 2
(+ 3 6) ;; Passo 1: atualizar a e b
(+ 2 7) ;; Passo 2
(+ 1 8) ;; Passo 3
(+ 0 9) ;; Passo 4: caso-base (a=0)
9       ;; Resultado

Exercício 1.10: Resposta

Os valores das expressões são:


(A 1 10)
1024 ;; Resposta

(A 2 4)
65536 ;; Resposta

(A 3 3)
65536 ;; Resposta

Definições matemáticas para (f n), (g n), (h n), (k n)


(f n) ;; Sendo n > 0
;; f(n) = 2n

(g n) ;; Sendo n > 0
;; g(n) = 2^n

(h n) ;; Sendo n > 0
;; h(n) = 2↑↑n = 2^(h(n-1)) = 2^(2^(h(n-1))) = 2^(2^(2^(...^(2))))
;; Exemplo:
;;;; h(1) = 2
;;;; h(2) = 2^2 = 4
;;;; h(3) = 2^(2^2) = 16
;;;; h(4) = 2^(2^(2^2)) = 65536

;; (k n) => 5n^2

1.2.2 Recursão em Árvore

Padrão de função recursiva que gera estruturas semelhantes a árvores.
Cada chamada recursiva cria "ramos" que se dividem até atingir um caso-base.
O número de passos cresce rapidamente, proporcional ao número de nós na árvore. O crescimento temporal é exponencial.
O espaço necessário cresce proporcional à profundidade da árvore. Apenas os nós ativos na recursão são armazenados na memória. O crescimento espacial é linear.
É natural para problemas com estruturas hierárquicas (ex: árvores de dados). Mas é ineficiente para entradas grandes devido a cálculos redundantes e aí entra a função interativa.

Exercício 1.11: Resposta

Regra:

f (n) = {\begin{cases} n & para n < 3 \\ f (n - 1) + 2 f (n - 2) + 3 f (n - 3) & para n \geq 3 \end{cases}}

Para f(n) como procedimento recursivo:


(define (f n)
  (if (n < 3)
      n
      (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3)))
      )
  )
)

Para f(n) como procedimento interativo:

Se n < 3 é retornado n


(if (n < 3) n ...)

Preciso armazenar os valores:

f(n-1) = a
f(n-3) = b
f(n-2) = c

O valor base é quando n = 3, então:

Valor inicial: a = 2
Valor inicial: b = 1
Valor inicial: c = 0

Quando n > 3 é preciso calcular várias vezes f(n), para isso preciso atualiza os valores durante o processo a fim de não criar um processo recursivo, onde:
- c = b
- b = a
- a = f(n-1) + 2f(n-2) + 3f(n-3)
Logo preciso de um loop e uma variável de controle que pare o loop quando igual ao valor de n, já que o cálculo será feito a partir do valor de base e o cálculo repetirá n vezes:


(define (loop controle a b c)
  (if (= n controle)
      controle
      (loop (+ 1 controle)
            (+ a (* 2 b) (* 3 c))
            a                  
            b
            
      )
  )
)

O Procedimento completo fica:


(define (i n)
  (define (loop controle a b c)
    (if (= n controle)
        a                           ;; Aqui retorna o valor do cálculo
        (loop                       ;; Chamada para atualizar os valores
              (+ 1 controle)        ;; Mecanismo de stop
              (+ a (* 2 b) (* 3 c)) ;; Novo 'a'
              a                     ;; Novo 'b'                  
              b                     ;; Novo 'c'
        )
    )
  )

  (if (< n 3)
      3
                                    ;; Aqui determino o valor inicial de 'a',
                                    ;; 'b', 'c' e da variável de controle:
                                    ;; (loop <a> <b> <c> <controle>)  
      (loop 2 2 1 0)   
  )
)

Exercício 1.12: Resposta

O triangulo é formado por linhas (l)
O número da linha determina quantos números haverá nela, exemplo:

Linha 1 = 1 número
Linha 2 = 2 números
Linha 3 = 3 números
...

A primeira posição p na linha pode ser zero ou 1, vou usar 1 como posição inicial, pois se eu usar 0 o número de elementos em cada linha será l + 1 e não l. O Que evita eu ter que implementar algo para deixar natural para o usuário final.

As outras posição é definida pela soma de 2 números da linha de anterior, sendo:

O primeiro número da mesma posição:


(+ (- l 1)  ;; Linha Anterior
   (p))     ;; Posição do número atual

O segundo número da posição anterior


(+ (- l 1)  ;; Linha Anterior
   (+ p 1)) ;; Posição do número atual

Então a função fica:


(define (pascal l p)
  (cond 
    ;; Verifica se a posição é inválida
    ((or (< p 1) (> p l)) 0) ;; Retorna 0 para posições inválidas

    ;; Converte linhas negativas para positivas
    ((<= l 0) (pascal (abs l) p)) ;; Evita linhas *negativas

    ;; Casos-base: bordas da linha
    ((= p 1) 1) ;; Primeira posição da linha → 1
    ((= p l) 1) ;; Última posição da linha → 1

    ;; Passo recursivo: soma dos dois elementos acima
    (else 
      (+ (pascal (- l 1) p)        ;; Elemento acima (n-1, p)
          (pascal (- l 1) (- p 1))  ;; Elemento acima à esquerda (n-1, p-1)
      )
    ) 
  )      
)

Exercício 1.13: Resposta

...

1.2.3 Ordens de Crescimento

Ordens de Crescimento são uma maneira de descrever como o consumo de recursos (como tempo ou espaço) de um processo computacional aumenta à medida que o tamanho do problema cresce. Imagine que você tem um algoritmo que leva R(n) passos para ser executado, onde n é o tamanho da entrada. Se R(n) = Θ(n²), isso significa que, para entradas grandes, o tempo de execução do seu algoritmo crescerá aproximadamente como o quadrado do tamanho da entrada:

Processo Linear:
- Se um processo requer Θ(n) passos, o número de operações cresce linearmente com n.
- Exemplo: Se você dobrar o tamanho do problema n, o número de operações também dobrará.
Processo Quadrático:
- Se um processo requer Θ(n²) passos, o número de operações cresce quadraticamente com n.
- Exemplo: Dobrar o tamanho do problema quadruplicará o número de operações.
Processo Exponencial:
- Se um processo requer Θ(ϕⁿ) passos (onde ϕ é a razão áurea), o número de operações cresce exponencialmente com n.
- Exemplo: Cada incremento no tamanho do problema multiplicará o número de operações por um fator constante.
Processo Logarítmico:
- Se um processo requer Θ(log n)passos, o número de operações cresce lentamente, mesmo quando n aumenta significativamente.
- Exemplo: Dobrar o tamanho do problema aumenta o número de operações por uma quantidade constante.
Processo Não Primitivo-Recursivo:
- Se um processo requer uma função não primitiva-recursiva, como a Função de Ackermann A(n, n), o número de operações cresce de forma extremamente rápida, ultrapassando qualquer função primitiva-recursiva.
- Exemplo: A Função de Ackermann A(4, n) já produz números tão grandes que são praticamente incomputáveis para valores modestos de n.
- Característica: O crescimento é tão acelerado que não pode ser descrito por funções como exponenciais, fatoriais ou torres de potências.

Tipo de Processo	Ordem de Crescimento	Exemplo de Comportamento
Logarítmico	Θ(log n)	Crescimento muito lento.
Linear	Θ(n)	Crescimento proporcional ao tamanho do problema.
Quadrático	Θ(n²)	Crescimento rápido, mas gerenciável.
Exponencial	Θ(ϕⁿ)	Crescimento explosivo, impraticável para n grande.
Não Primitivo-Recursivo	Θ(A(n, n))	Crescimento extremamente rápido, incomputável.

Exercício 1.14: Resposta

Árvore ilustrativa do processo count-change:

Figura retirada de Sicp-Solutions

A Imagem representa:


(count-change 11) ;; Chamada Inicial
;; (cc 11 5) → (+ (cc 11 4) (cc -39 5))
;; (cc 11 4) → (+ (cc 11 3) (cc -14 4))
;; (cc 11 3) → (+ (cc 11 2) (cc   1 3))
;; (cc 11 2) → (+ (cc 11 1) (cc   6 2))
;; (cc 11 1) → (+ (cc 11 0) (cc  10 1))
;; (cc 10 1) → (+ (cc 10 0) (cc   9 1))
;; (cc  9 1) → (+ (cc  9 0) (cc   8 1))
;; (cc  8 1) → (+ (cc  8 0) (cc   7 1))
;; (cc  7 1) → (+ (cc  7 0) (cc   6 1))
;; (cc  6 1) → (+ (cc  6 0) (cc   5 1))
;; (cc  5 1) → (+ (cc  5 0) (cc   4 1))
;; (cc  4 1) → (+ (cc  4 0) (cc   3 1))
;; (cc  3 1) → (+ (cc  3 0) (cc   2 1))
;; (cc  2 1) → (+ (cc  2 0) (cc   1 1))
;; (cc  1 1) → (+ (cc  1 0) (cc   0 1))
;; (cc  0 1) → Retorna 1.
4

Análise de crescimento espacial⁵:

Não há estruturas de dados além das variáveis locais.
A profundidade da recursão é proporcional ao valor de amount.
As variáveis locais são constantes em cada chamada. Como o espaço é dominado pala profundidade de chamadas de amunt o crescimento é linear Θ(n)

Análise de crescimento temporal⁶:

O algoritmo é recursivo, sem loops explícitos.
Cada chamada recursiva gera duas novas chamadas:

Uma para (cc amount (- kinds-of-coins 1))
Outra para (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)
O número de chamadas cresce exponencialmente com o valor de amount, porque cada chamada pode gerar duas novas chamadas.

Conclusão:

Ordem de Crescimento Espacial: Θ(n)
Ordem de Crescimento Temporal: Θ(2ⁿ)

Exercício 1.15: Resposta

O procedimento p é aplicado 5 vezes quando (sine 12.15)


(sine 12.15)
=> (p (sine 4.05))                 ;; 1ª aplicação de p
=> (p (p (sine 1.35)))             ;; 2ª aplicação de p
=> (p (p (p (sine 0.45))))         ;; 3ª aplicação de p
=> (p (p (p (p (sine 0.15)))))     ;; 4ª aplicação de p
=> (p (p (p (p (p (sine 0.05)))))) ;; 5ª aplicação de p
=> (p (p (p (p (p 0.05)))))        ;; Caso base atingido
0.05

No procedimento sine, o argumento a é reduzido exponencialmente a cada passo (dividido por 3), o que caracteriza um processo de divisão recursiva. Isso difere de um crescimento linear ou exponencial:

Redução por fator constante (3): $\begin{matrix} \frac{a}{3^{k}}, k = 1, 2, 3, \dots \end{matrix}$

Se fosse linear, os passos seriam proporcional a a (ex: k = a/3)
Se fosse exponencial, passos cresceriam como 3^k (impraticável).

Por que logaritmo? O logaritmo resolve equações onde a incógnita está no expoente. Na condição $\frac{a}{3^{k}} \leq 0.1$ , isolamos 3 ^k e aplicamos log₃ para extrair k:

\begin{matrix} 3^{k} \geq \frac{a}{0.1} \Rightarrow k \geq \log_{3} (\frac{a}{0.1}) \end{matrix}

Simplificação: Usando a propriedade $\log_{3} (\frac{a}{b}) = \log_{3} (a) - \log_{3} (b)$ , obtemos:

\begin{matrix} \log_{3} (\frac{a}{0.1}) = \log_{3} (a) - \log_{3} (0.1) \end{matrix}

O uso do logaritmo é natural já que a redução é exponencial (base 3). Isso resulta em uma complexidade espacial e temporal $Θ (\log a)$ , muito mais eficiente que soluções lineares ( $Θ (a)$ ) ou exponenciais ( $Θ (3^{k})$ ).

1.2.4 Exponenciação

Exercício 1.16: Resposta

Exponenciação: bⁿ
Redução por quadrados sucessivos (para n par):
Se n é par, podemos calcular bⁿ de forma mais rápida:
$b^{n} = {(b^{\frac{n}{2}})}^{2}$
Exemplo prático:

$2^{8} \to (^{2})^{4})^{2} \to (^{4})^{2})^{2} \to 16^{2} = 256$

Por que isso funciona? Cada vez que elevamos ao quadrado, o expoente cai pela metade. Isso reduz o número de multiplicações!
Passos logarítmicos (por que é rápido?):
- Para n = 8: $2^{8} \to 3 passos (\log_{2} 8 = 3)$
- Para n = 16: $\log_{2} 16 = 4 passos$
Comparação: Se dobrar (ex: 8 → 16), o número de passos só aumenta em 1! Isso é o que chamamos de crescimento logarítmico.
E se n for ímpar?
Exemplo para 3⁵:

$3^{5} = 3 \times 3^{4} \to 3 \times 3^{2^{2}} = 3 \times 81 = 243$

Observação: Mesmo com um passo extra (para ajustar o expoente ímpar), o total de operações ainda é proporcional a log(n).

Formalização:

b^{n} = {\begin{cases} 1 se n = 0, \\ {(b^{n / 2})}^{2} se n é par, \\ b \times b^{n - 1} se n é ímpar. \end{cases}


(define (expt-with-successive-squares
          base
          exponent
          current-product
        )
  (cond ((= exponent 0) 
          1
        )
        ((even? exponent)
          (expt-with-successive-squares 
            (* base base)
            (/ exponent 2)
            current-product)
        )
        (else
          (expt-with-successive-squares
            base
            (- exponent 1)
            (* base current-product)
          )
        )
  )
)

Exercício 1.17: Resposta

⁴ Uma função é tail-recursive se a última ação executada antes de retornar for uma chamada direta a si mesma (sem operações pendentes). Em outras palavras, a chamada recursiva é a última operação no fluxo de execução, não havendo necessidade de processamento adicional após o retorno da recursão.

Por que é importante? Em linguagens que suportam otimização de chamada de cauda (TCO), como Scheme, processos tail-recursive são executados em espaço constante (Θ(1))^1.2.3, ou seja, não acumulam pilha de chamadas. Isso evita estouro de pilha (stack overflow) para grandes iterações e torna a recursão tão eficiente quanto um loop imperativo.

⁵ Discas: Ordem de Crescimento Temporal:

Conte o número de operações:

Pergunte-se: "Quantas operações o algoritmo realiza para uma entrada de tamanho n?".
Como usar: Para loops, conte o número de iterações. Para recursão, analise o número de chamadas.

Analise estruturas de repetição (loops):

Loops aninhados geralmente indicam crescimento polinomial (ex.: O(n²) para dois loops).
Como usar: Identifique o número de loops e sua relação com o tamanho da entrada.

Verifique chamadas recursivas:

Recursão pode levar a crescimento exponencial O(2ⁿ) ou logarítmico O(log n), dependendo de como o problema é dividido.
Como usar: Analise quantas chamadas são geradas em cada passo e como o tamanho do problema é reduzido.

Observe operações internas:

Operações dentro de loops ou recursões contribuem para o tempo total.
Como usar: Multiplique o número de iterações pelo custo das operações internas.

Use a notação Big-O:

Simplifique a análise ignorando constantes e termos de menor ordem.
Como usar: Foque no termo dominante da função de custo.

⁶ Discas: Ordem de Crescimento Espacial:

Analise a estrutura de dados utilizada:

Estruturas como arrays, listas ou matrizes ocupam espaço proporcional ao tamanho da entrada.
bⁿ Como usar: Verifique o tamanho das estruturas de dados em função de n.

Verifique a profundidade da recursão:

Em algoritmos recursivos, o espaço é determinado pela profundidade da pilha de chamadas.
Como usar: Analise quantas chamadas recursivas são feitas antes de atingir o caso base.

Observe variáveis temporárias:

Variáveis criadas em cada iteração ou chamada recursiva contribuem para o espaço.
Como usar: Conte o número de variáveis e seu tamanho em função de n.

Verifique alocações dinâmicas:

Alocações de memória durante a execução (ex.: criar novas listas) aumentam o espaço.
Como usar: Identifique quanta memória é alocada em função de n.

Analise o uso de memória em função da entrada:

Pergunte-se: "Como o uso de memória aumenta à medida que a entrada cresce?".
Como usar: Relacione o espaço utilizado com o tamanho da entrada n.