CODEWITHSUNDEEP
schemelispracket
Tryer outer
Tryer outer

Reputation: 47

Every procedure from recursive to iterative and vice versa?

Can you turn every recursive procedure with a recursive proces from recursive (even tree recursive) to iterative and vice versa (in Scheme)? By changing the way the code is written?

Upvotes: 0

Views: 163

Answers (2)

Sylwester
Sylwester

Reputation: 48755

You have to distinguish between a recursive function/procedure and recursive process. Eg. imagine walking a binary tree. That is surely a recursive process since no matter how you implement it you need to backtrack so if you make it iterative you will have some sort of data structure replacing the system stack that is being used in a recursive solution.

Using the same algorithm you cannot transform a recursive process into an iterative one. That is impossible.

However, some algorithms might be replaced by others that does other things. A great example of this is the fibonacci procedure. Here is a tree walk version:

(define (fib-rec n)
  (if (< n 2)
      n
      (+ (fib-rec (- n 1)) 
         (fib-rec (- n 2)))))

And you have probably seen this version whose algorithm just iterates a window of the values from bottom and up to the answer:

(define (fib-iter n)
  (let loop ((n n) (a 0) (b 1))
    (if (zero? n)
        a
        (loop (- n 1) b (+ a b)))))

These are not the same algorithm. A recursive to iterative conversion of fib-rec would be something like this:

(define (fib n)
  (let loop ((jobs '(fib)) (args (list n)))
    (cond ((null? jobs)
           (car args))
          ((eq? (car jobs) 'swap)
           (loop (cdr jobs)
                 (list* (cadr args) (car args) (cddr args))))
          ((eq? (car jobs) 'add)
           (loop (cdr jobs)
                 (cons (+ (car args)
                          (cadr args))
                       (cddr args))))
          ((< (car args) 2) 
           (loop (cdr jobs) args))
          (else 
           (loop (list* 'fib 'swap 'fib 'add (cdr jobs))
                 (list* (- (car args) 2) (- (car args) 1) (cdr args)))))))

This does pretty much the same as fib-rec except it uses an operations list and an argument stack. It is a recursive process but te procedure is tail recursive and thus iterative.

An inheritly iterative process cannot be converted to a recursive one without changeing the algorithm. Think of it as having the fib-iter and rewriting it to a fib-rec. Also since Scheme doesn't have primitive looping constructs except recursion all iterative processes are done with recursion. If you read the reports you'll see that do and other looping constructs is derives syntax and what recursion they turn into.

Upvotes: 1

Gwang-Jin Kim
Gwang-Jin Kim

Reputation: 9865

Yes, definitely. Recursive function have always a breaking condition. Sometimes the breaking condition is about a list which is used-up and thus becomes null from recursive call to next recursive call. In that case, you can handle it via a for-loop over the list. Sometimes the breaking condition is about some number decreasing or sth else - then one could use a while loop to test for the breaking condition.

Upvotes: 0

Related Questions