CODEWITHSUNDEEP
recursionfunctional-programmingschemeracket
dahui
dahui

Reputation: 2166

What are the differences between these two racket functions in terms of speed/efficiency?

(define (myminus x y)
  (cond ((zero? y) x)
        (else (sub1 (myminus x (sub1 y))))))

(define (myminus_v2 x y)
  (cond ((zero? y) x)
        (else (myminus_v2 (sub1 x) (sub1 y)))))

Please comment on the differences between these functions in terms of how much memory is required on the stack for each recursive call. Also, which version might you expect to be faster, and why?

Thanks!

Upvotes: 1

Views: 143

Answers (2)

Sylwester
Sylwester

Reputation: 48745

myminus creates y continuations to sub1 what the recursion evaluates to. This means you can exhaust rackets memory limit making the program fail. In my trials even as little as 10 million will not succeed with the standard 128MB limit in DrRacket.

myminus_v2 is tail recursive and since racket have same properties as what scheme requires, that tail calls are to be optimized to a goto and not grow the stack, y can be any size, i.e. only your available memory and processing power is the limit to the size.

Your procedures are fine examples of peano arithmetic.

Upvotes: 2

WorBlux
WorBlux

Reputation: 1413

They should both have a number of steps proportional to y.

The second one is a tail call meaning the interpreter can do a tail elimination meaning it takes up a constant space on the stack whereas in the first the size of the stack is proportional to Y.

Upvotes: 3

Related Questions