Recursão e Procedimentos de Alta Ordem

Lucas Vieira

Iterando sobre listas

Exemplo 1: Somando os elementos de uma lista

#lang sicp

(define (sum-of-list lst)
  (if (null? lst)
      0
      (+ (car lst)
         (sum-of-lst (cdr lst)))))

Exemplo 2: Elevando elementos de uma lista ao quadrado

#lang sicp

(define (square x)
  (* x x))

(define (square-list lst)
  (if (null? lst)
      '()
      (cons (square (car lst))
            (square-list (cdr lst)))))

Procedimentos como argumentos

Exemplo 1: Função de soma genérica

#lang sicp

(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (1+ a) b))))

(define (sum-cubes a b)
  (if (> a b)
      0
      (+ (cube a) (sum-cubes (1+ a) b))))

Exemplo 2: Pi-soma

A soma a seguir converge vagarosamente para \(\frac{\pi}{8}\):

\(\frac{1}{1 \cdot 3} + \frac{1}{5 \cdot 7} + \frac{1}{9 \cdot 11} + \dots\)

#lang sicp

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2)))
         (pi-sum (+ a 4) b))))

Abstração de um procedimento genérico

  • Funções também são valores.
  • Funções podem ser passadas como parâmetro.
  • Funções não precisam ser previamente definidas.

Expressões lambda

#lang sicp

;; Este procedimento
(define (square x)
  (* x x))

;; Equivale a este
(define square
  (lambda (x)
    (* x x)))

Sintaxe de uma expressão lambda

(lambda (<parâmetros formais>) <corpo>)

Não é estritamente necessário dar um nome a um procedimento para utilizá-lo:

#lang sicp

((lambda (x) (+ x 2))
 4)
;; => 6

Exemplo 2: Função map

A função map aplica um certo procedimento a cada elemento de uma lista, criando outra lista no processo.

#lang sicp

(define square (lambda (x) (* x x)))

(map square '(1 2 3 4)) ;; => (1 4 9 16)

(map (lambda (x) (1+ x))
     '(1 2 3 4))
;; => (2 3 4 5)

Implementação

#lang sicp

(define (map proc lst)
  (if (null? lst)
      '()
      (cons (proc (car lst))
            (map proc (cdr lst)))))

Exemplo 3: Função de soma genérica

#lang sicp

(define (generic-sum-iter acc lst)
  (if (null? lst)
      acc
      (generic-sum-iter (+ acc (car lst))
                        (cdr lst))))

(define (generic-sum lst)
  (generic-sum-iter 0 lst))

Exercícios

Exercício 1

A função de soma genérica pode ser considerada uma especialização da função fold, que toma três elementos:

  • Uma função de acúmulo (proc): por exemplo, a função +;
  • Um acumulador (acc): por exemplo, o valor 0;
  • Uma lista (lst).

Desta forma, poderíamos reescrever generic-sum assim:

(define (generic-sum lst)
  (fold + 0 lst))

Implemente a função fold.

(define (fold proc acc lst)
  ...)