Даже? функция в схеме (Dr. Racket)

Question

Я пытаюсь написать программу на Схеме, чтобы вычислить результат функции мощности, используя алгоритм/рекурсию быстрой мощности. Алгоритм должен быть правильным, но где-то мой синтаксис выключен. Программа компилируется, но когда я ввожу базу и exp для тестирования, Dr. Racket зависает и исчерпывает память. Нелегко найти онлайн-примеры того, как должна выглядеть функция (четная?) В коде схемы. Я думаю, это может отбросить мой синтаксис. Новая схема, поэтому любая помощь была бы высоко оценена.

(define (powFun base exp) 
    (if (= exp 0)      //base case 
    1          
     (even? exp      //if exp is even 
      (* 
      (powFun base (/ exp 2)) 
      (powFun base (/ exp 2)) 
     ) 

     (* 
      (powFun base (- exp 1))  // else if exp is odd 
      base 
     ) 
    ) 
) 

)

Answer 1

even? не похож на if - вы используете его для проверки, один номер есть.
Он не имеет «ветви»:

> (even? 2) 
#t 
> (even? 2 "even" "odd") 
. . ..\..\Program Files (x86)\Racket\share\pkgs\drracket\drracket\private\rep.rkt:1088:24: even?: arity mismatch; 
the expected number of arguments does not match the given number 
    expected: 1 
    given: 3 
    arguments...: 
    2 
    "even" 
    "odd" 

Вы можете использовать его в качестве теста на условный:

> (if (even? 2) "even" "odd") 
"even" 

Если вы хотите проверить несколько условий, это удобно использовать cond вместо if:

> (define x 3) 
> (cond ((= x 1) "one") 
     ((even? x) "even") 
     (else "odd")) 
"odd" 

Но это не повод для DrRacket "замораживания".

Причина этого является то, что разделение не является целочисленным делением, но на самом деле производит точную дробную результат:

> (/ 1 2) 
1/2 
> (/ (/ 1 2) 2) 
1/4 
> (/ (/ (/ 1 2) 2) 2) 
1/8 

так что вы никогда не достигнете случая завершающего.

Вы должны использовать quotient процедуры:

> (quotient 3 2) 
1 
> (quotient 2 2) 
1 
> (quotient 1 2) 
0 

Воспользовавшись sqr процедуры и изменив кронштейны от «стиля C» в стиле «схемы», он может выглядеть следующим образом:

(define (powFun base exp) 
    (if (= exp 0) 
     1          
     (if (even? exp) 
      (sqr (powFun base (quotient exp 2))) 
      (* (powFun base (- exp 1)) base)))) 

Или

(define (powFun base exp) 
    (cond ((= exp 0) 1)          
      ((even? exp) (sqr (powFun base (quotient exp 2)))) 
      (else (* (powFun base (- exp 1)) base)))) 

> (powFun 2 3) 
8 
> (powFun 2 0) 
1 
> (powFun 2 300) 
2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376 

Примечание стороны: победа взаимодействия dow чрезвычайно полезна для тестирования небольших частей кода, когда вы ищете проблему.

Answer 2

if может принимать только максимум 2 статьи, then и else без ключевого слова. В этой ситуации вы можете использовать вложенные if или cond. Ниже приведен пример cond:

(cond ((= expr 0) 1) 
     ((even? exp) #| do even ... |#) 
     (else #| do odd |#)) 

Answer 3

Вы, кажется, использует even?, как если бы это был какой-то макрос, который ведет себя как if. Но even? - это регулярная функция, которая принимает один аргумент, поэтому вы должны были написать (even? exp), а не (even? exp evaluate-if-even evaluate-if-not-even). Это означает, что возвращаемое значение even? нуждается в собственном if выражение:

(if base-case 
    1 
    (if (even? exp) 
     evaluate-if-even 
     evaluate-if-not-even)) 

... что означает, что вы должны использовать cond вместо этого.

Или вы можете определить макрос, который работает так, как вы думали even?. Давайте назовем это if-even:

(define-syntax if-even 
    (syntax-rules() 
     ((_ n evaluate-if-even evaluate-if-not-even) 
     (if (even? n) evaluate-if-even evaluate-if-not-even)))) 

Затем замените even? в исходной программе с if-even. Исправлено использование вами even?, а затем переход на cond вместо if - лучший вариант.