CODEWITHSUNDEEP
functional-programmingiterationschemetail-recursionsicp
Enlico
Enlico

Reputation: 28490

Is an iterative process that returns a list with size that increases by iteration any different from an one that returns a scalar?

This actually comes from me initially misreading the text of Exercise 1.12.

The request is indeed to

Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

I crucially mistook recursive for iterative, and spent quite a bit trying to understand where in the world I could come up with a number of numbers that could describe the state of the computation at any given stage, but I didn't come up with anything. Quite the opposite, I think that you can't just represent the state of the computation of the triangle with a constant number of scalars.

So I eventually re-read the exercise statement, realized my mistake and completed the exercise the intended way.

But still, the fact that an iterative process for that solution is not required in following exercises either, made me think that maybe such a solution either doesn't exist, or it has some properties that make it fundamentally different from other recursive procedures implemented as iterative processes.

Anyway, I was curious, so thought: what if the state is not a number but a list? In that case, pretty naturally the state of the computation is the previous row of the triangle; i.e., all one needs to compute each and all of the elements of the n-th row of the triangle is the n-1-th row.

So I came up with this procedure

(define (pascal i j)
  (define (update t)
    (concat (cons 1 (zipWith+ (cdr t) t)) '(1)))
  (define (pascal-impl i t)
    (if (= i 0)
        t
        (pascal-impl (- i 1) (update t))))
  (element (pascal-impl i '(1)) j))

where pascal-impl carries on the state t of the computation of the trianlge (a row) and the count i. Then the main function pascal picks the appropriate entry from the required row.

Now, leaving aside the understandable inefficiency due to the usage of a bare list, I was wondering

I'm assuming these utilities or, again, a better performing version of them, are available:

(define (zipWith+ a b)
  (if (null? a)
      '()
      (cons (+ (car a) (car b)) 
            (zipWith+ (cdr a) (cdr b)))))

(define (concat a b)
  (if (null? a)
      b
      (cons (car a) 
            (concat (cdr a) b))))

(define (element xs i)
  (if (= i 0)
      (car xs)
      (element (cdr xs) (- i 1))))

Upvotes: 1

Views: 57

Answers (1)

Will Ness
Will Ness

Reputation: 71119

"Iterative" simply means not recursive. Thus, your pascal-impl, being tail-recursive, actually describes a loop, so is indeed iterative.

The size of the state is indeed an orthogonal issue. In your function it is indeed growing as ~ 2n for the nth step.

As an aside, zipWith+ can be coded as a right fold over the list's tails (i.e. its iterated cdrs), eliminating the need for the concat:

(define (next-row a)
  (define (go a)
    (cond 
       ((null? a)
          '())
       ((null? (cdr a))
          (list 1))
       (else
          (cons (+ (car a) (cadr a))
                (go (cdr a))))))
  (cons 1 (go a)))

Another line of optimization is, since you only produce one element in the end, let its index guide your iteration and produce only as much of the triangle as needed, which will be of a skewed rhombic shape.

Upvotes: 1

Related Questions