CODEWITHSUNDEEP
recursioniterationlispracketsicp
user4206400
user4206400

Reputation:

SICP - Recursive or iterative process?

I am using the SICP book and I am struggling with the concepts of recursive versus iterative process. At the question 1.17 they ask this:

Exercise 1.17. The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:

(define (* a b)
  (if (= b 0)
  0
  (+ a (* a (- b 1)))))

This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

(Source: https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4)

I did the following code, which appears to be right:

(define (* a b)
  (cond ((= b 1) a)
        ((even? b) (* (double a) (halve b)))
        (else (+ a (* (double a) (halve (- b 1)))))))

If a use trace, a debugging built-in function in Dr. Racket, inputing 343 and 799 I get:

(require racket/trace)
(trace *)
(* 343 799)

>(* 343 799)
> (* 686 399)
> >(* 1372 199)
> > (* 2744 99)
> > >(* 5488 49)
> > > (* 10976 24)
> > > (* 21952 12)
> > > (* 43904 6)
> > > (* 87808 3)
> > > >(* 175616 1)
< < < <175616
< < < 263424
< < <268912
< < 271656
< <273028
< 273714
<274057
274057
>

I am confused. The process that I created has a recursive definition but it seems to have a recursive nature and an iterative nature. Am I wrong? Can a process be iterative and recursive?

I see the recursive nature with the tree design while debugging it. And I see the iterative nature since I am using the variable/parameter "a" as a state variable. Did I misunderstand something?

Upvotes: 0

Views: 951

Answers (1)

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

Reputation: 236004

The process shown in your code is recursive - you can see that at each call, in the else part there's an operation still pending: an addition. Typically, an iterative process passes the answer around as a parameter (the accumulator) in such a way that the recursive call is in tail position - that is, it's the last thing we do, with no pending operations left.

In your stack trace it's obvious that a recursive process is occurring, the calls to the * procedure pile up to a certain point, and then start to go back - it looks like a triangle. Compare it with this, a truly iterative multiplication; here we don't see the triangle shape when running trace, and the procedure runs in a constant amount of space:

(define (mul a b)
  (define (iter count acc)
    (if (zero? count)
        acc
        (iter (- count 1) (+ acc a))))
  (iter b 0))

(trace mul)
(mul 343 799)

>(mul 343 799)
<274057
274057

Upvotes: 1

Related Questions