CODEWITHSUNDEEP
recursionschemetail-recursionbit
oy1
oy1

Reputation: 87

Is this Scheme function tail recursive?

The function receives a number and returns the number of bits that would have been required to be “on” in order to represent the input number in binary base. For example, the number 5 is represented as 101 in binary and therefore requires two bits to be “on”. I need to know if the function I wrote is tail recursion. If not, how can I turn it to tail recursion? Thanks!

My function:

(define (numOfBitsOn number)
  (define (numOfBitsOn-2 number acc)
      (if (> number 0)
           (if (odd? number)
               (numOfBitsOn-2(/(- number 1) 2) (+ acc (modulo number 2)))
               (numOfBitsOn-2 (/ number 2) acc))
           acc))
  (numOfBitsOn-2 number 0))

Upvotes: 1

Views: 184

Answers (1)

soegaard
soegaard

Reputation: 31147

DrRacket can help you determine whether a call is in tail position or not. Click the "Syntax Check" button. Then move the mouse pointer to the left parenthesis of the expression in question. In an example I get this:

TCO example

The purple arrow shows that the expression is in tail-position.

From the manual:

Tail Calls: Any sub-expression that is (syntactically) in tail-position with respect to its enclosing context is annotated by drawing a light purple arrow from the tail expression to its surrounding expression.

Upvotes: 3

Related Questions