CODEWITHSUNDEEP
recursionschemeiteration
John NG
John NG

Reputation: 29

Scheme R5RS, recursion or iterative?

I have programmed a scheme code with 2 functions that plusses 1 to the argument, and subtracts 1 from the argument. I've now programmed a function to do this automatically, but I don't know if it's recursive or iterative. Here's the whole code:

(define add1
  (lambda (x)
    (+ x 1)))

(define sub1
  (lambda (x)
    (- x 1)))

(define plus
  (lambda (x y)
    (if (zero? y)
        x
        (plus (add1 x) (sub1 y)))))

Now my question is, what kind of function is plus? Recursive, or iterative, and why?

Upvotes: 0

Views: 1244

Answers (2)

Sylwester
Sylwester

Reputation: 48745

As code goes it is a recursive procedure. The process however is iterative since it does the recursion in tail position.

In Scheme you can write both iterative and recursive processes with recursive functions.

Example:

;; iterative process
;; recursive (inner) procedure
(define (fib n)
  (define (fib n a b)
    (if (zero? n)
        a
        (fib (- n 1) b (+ a b)))
  (fib n 0 1))

;; recursive process
;; recursive procedure
(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

You can also write both recursive and iterative processes with loop constructs, though in Scheme such loop constructs are really just syntactic sugar for tail recursion. It's fairly common in other languages though in order to be able to recurse deeper.

Example:

;; iterative process
;; iterative procedure  (do)
(define (fib n)
  (do ((n n (- n 1))
       (a 0 b)
       (b 1 (+ a b)))
      ((zero? n) a)))

;; recursive process
;; iterative procedure (do)
(define (fib n)
  (let ((work (list n #f)))
    ;; push x-1 and x-2 onto work
    (define (push-reduce! x)
      (set! work 
            (cons (- x 1) 
                  (cons (- x 2) work))))
    ;; pop top of work
    (define (pop)
      (let ((v (car work)))
        (set! work (cdr work))
        v))

    ;; find fibonacci with a iterative
    ;; (and ugly) do loop
    (do ((n 0 (if (< c 2) (+ n c) (begin (push-reduce! c) n)))
         (c (pop) (pop)))
      ((not c) n))))

The last one is simply horrible Scheme as should be avoided, but it's pretty much used to avoid stack overflows in other languages.

Upvotes: 1

&#211;scar L&#243;pez
&#211;scar L&#243;pez

Reputation: 236004

Syntactically, the plus function is recursive: clearly, it's calling itself. The interesting question is: what kind of process does it generate? Given that it was written in a tail-recursive fashion (intuitively: there's nothing left to do after the recursive call), we can state that the process it generates is iterative. For a more detailed discussion of procedures and the processes they generate, refer to SICP.

Upvotes: 5

Related Questions