схема итерации суммирования в списках - PullRequest
Новая
       19

схема итерации суммирования в списках

0 голосов
/ 19 ноября 2018

Я хочу спросить, не хочет ли кто-нибудь помочь мне с кодом итеративной схемы, который дает сумму двух списков. У меня уже есть рекурсивная версия кода. 

(define (sum-lists l1 l2)(cond ((and (null? l1) (null? l2)) '())
    ((null? l1) l2)
    ((null? l2) l1)
    (else (cons (+ (car l1) (car l2)) (sum-lists (cdr l1) (cdr l2))))))

1 Ответ

0 голосов
/ 19 ноября 2018

Общий рецепт "итеративной процедуры":

  1. Напишите вспомогательную функцию, которая принимает параметр аккумулятора.
    Создайте каждый промежуточный результат в аккумуляторе.
  2. Когда вы закончите рекурсию, верните аккумулятор.
  3. Передайте ему подходящий начальный аккумулятор.

Обычно при преобразовании списков накапливается результат в обратном порядке, а затем, когда вы закончите, результат инвертируется.

Тривиальный пример, увеличивающий каждый элемент списка на единицу: 

(define (add-1 ls)
  (if (null? ls)
      '()
      (cons (+ 1 (car ls)) (add-1 (cdr ls)))))

Чтобы сделать его итеративным, создайте вспомогательную функцию, в которой вы cons собираете аккумулятор вместо рекурсивного результата: 

(define (add-one ls acc)
  (if (null? ls)
      (reverse acc)
      (add-one (cdr ls) (cons (+ 1 (car ls)) acc))))

(Обратите внимание, что за исключением введения acc, рекурсия содержит те же части, что и раньше, но в другом порядке.)

Затем вы запускаете его с пустым аккумулятором: 

(define (add-1 ls)
  (add-one ls '()))

В вашем случае несколько больше базовых случаев, так как вам нужно разместить входы разной длины.
Завершение его осталось как упражнение.

(Другое упражнение: выясните, почему ваше первое условие, (and (null? l1) (null? l2)), не нужно.)

...