Search code examples
recursionschemelispsicp

Can logical operators use tail-recursion

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

This code is from SICP, chapter 1.2.6. The procedure uses tail-recursion, so it doesn't cause linear recursion when computed, in other words it's iterative. If I rewrite the procedure using or / and instead of cond, will it cause linear recursion?

(define (fast-prime? n times)
  (or (= times 0)
      (and (fermat-test n) (fast-prime? n (- times 1)))))
Solution

  • The right-hand side of and and or are tail expressions (see R5RS section 3.5), so you can safely use those for iterative purposes.