как проверить, является ли число степенью двойки в схеме путем хвостовой рекурсии?

Question

(define (ispowerof2? n)
  (cond ((< n 1) #f)
    ((= n 1) #t)
    ((> (remainder n 2) 0) #f)
    (else (ispowerof2? (/ n 2)))))

Является ли этот код правильным и как написать ту же функцию с хвостовой рекурсией?

Answer 1

Не совсем.Строка:

(else (ispower2? (/ n 2)))))

Содержит ошибку - она ​​должна быть ispowerof2.В противном случае это хвостовая рекурсия.

Answer 2

Я согласен с двумя другими ответами. Для более глубокого объяснения: «хвостовая рекурсия» - это функция, в которой все рекурсивные вызовы находятся в хвостовой позиции. Это вызывает вопрос о том, что составляет хвостовой вызов.

Один из способов увидеть хвостовые вызовы - запустить эту функцию, используя степпер DrRacket. В частности, установите уровень языка «Начинающий студент» и нажмите кнопку «шаг» в этой программе:

(define (ispowerof2? n)
  (cond
   ((< n 1) false)
   ((= n 1) true)
   ((> (remainder n 2) 0) false)
   (else (ispowerof2? (/ n 2)))))

(ispowerof2? 36)

... затем шагайте вперед, пока не получите рекурсивный вызов:

(define (ispowerof2? n)
  (cond
   ((< n 1) false)
   ((= n 1) true)
   ((> (remainder n 2) 0) false)
    (else (ispowerof2? (/ n 2)))))

(ispowerof2? (/ 36 2)) 

Обратите внимание, что рекурсивный вызов находится на верхнем уровне; нет никакого «контекста», оборачивающего его, с кодом, который будет применен к результату вызова. Это то, что подразумевается под «хвостовым вызовом». Сравните это с функцией, которая вычисляет длину списка:

(define (len l)
  (cond
   ((empty? l) 0)
   (else (+ 1 (len (rest l))))))

(len (cons 3 (cons 4 empty))

Шагайте вперед, пока не получите рекурсивный вызов, и вы увидите это:

(define (len l)
  (cond
   ((empty? l) 0)
   (else (+ 1 (len (rest l))))))

(+ 1 (len (list 4)))

Видите, как рекурсивный вызов 'len' находится внутри (+ 1 ...) выражения? Это потому, что этот вызов не в хвостовой позиции; есть еще несколько выражений для оценки в этой функции после возврата рекурсивного вызова.

Answer 3

Да, это хвостовая рекурсия.:)