Основным представлением числа, которое захватило мир штурмом, является позиционная запись .Это представление тесно связано с понятием частных и остаточных операций, которое вы несколько видите из определения своей рекурсивной функции.Почему это так?
Давайте немного в стороне: позиционная нотация - не единственное жизнеспособное представление числа.Один из способов, который встречается очень часто, - это учетный подход, когда число равно нулю или на единицу больше, чем число.Мы можем использовать палочки.Поскольку мы говорим о программах, давайте использовать тип данных .
Number :== Zero
| Successor(n) where n is a number
. Считайте, что это число «Ноль или преемник другого числа».Или, чтобы закодировать его в Схеме, которая поддерживает структурированные представления (например, Racket), мы можем написать это:
(define-struct Zero ())
(define-struct Successor (n))
Например, представление three с этой нотацией будет (Successor (Successor (Successor (Zero))).(Это представление называется Peano, если я правильно помню.)
Функции, которые имеют дело с этим типом структурированного типа данных, часто имеют такую же форму , как и у самого типа данных.То есть функция, которая работает с представлением в Peano, будет выглядеть примерно так:
;; a peano-eating-function-template: peano-number -> ???
(define (a-peano-eating-function-template a-num)
(cond [(Zero? a-num)
...]
[(Successor? a-num)
...
(a-peano-eating-function-template (Successor-n a-num))
...]
, где ... будет чем-то конкретным для конкретной проблемы, которую вы пытаетесь решить с помощью чисел Peano.Речь идет о функциях, следующих структуре данных, над которыми они работают.В качестве конкретного примера функции поедания Пеано, вот тот, который превращает пианино в кучу звезд:
;; peano->stars: peano-number -> string
;; Turn a peano in a string of stars. We are all made of stars.
(define (peano->stars a-num)
(cond [(Zero? a-num)
""]
[(Successor? a-num)
(string-append "*"
(peano->stars (Successor-n a-num)))]))
В любом случае, типы данных естественным образом приводят к функциям с определенными формами.Это приводит нас к возвращению к позиционной записи.Можем ли мы захватить позиционную запись как тип данных?
Оказывается, мы можем!Позиционная запись, такая как десятичная запись, может быть описана аналогично тому, как работает описание числа Пеано.Давайте назовем это представление Base10 , где оно выглядит следующим образом:
Base10 :== Zero
| NonZero(q, r) where q is a Base10, and r is a digit.
Digit :== ZeroD | OneD | TwoD | ... | NineD
И если мы хотим получить конкретное представление о программировании на языке со структурами,
(define-struct Zero ())
(define-struct NonZero(q r))
(define-struct ZeroD ())
(define-struct OneD ())
(define-struct TwoD ())
(define-struct ThreeD ())
(define-struct FourD ())
;; ...
Например, число сорок два может быть представлено в Base10 как:
(NonZero (NonZero (Zero) (FourD)) (TwoD))
Yikes.Это выглядит немного ... безумно.Но давайте еще немного опираемся на это.Как и прежде, функции, которые работают с Base10, часто будут иметь форму, которая соответствует структуре Base10:
;; a-number-eating-function-template: Base10 -> ???
(define (a-number-eating-function-template a-num)
(cond
[(Zero? a-num)
...]
[(NonZero? a-num)
... (a-number-eating-function-template (NonZero-q a-num))
... (NonZero-r a-num)]))
То есть мы можем получить форму рекурсивной функции, которая работает на Base10 практически бесплатно, простоследуя структуре самой Base10.
... Но это сумасшедший способ иметь дело с числами, верно?Хорошо ... помните, что дурацкое представление для сорок два :
(NonZero (NonZero (Zero) (FourD)) (TwoD))
Вот еще один способ представить то же число.
((0 * 10 + 4) * 10 + 2)
Почти то же самоеидея.Здесь давайте избавимся от еще нескольких скобок.Мы можем представить сорок два с помощью следующих обозначений:
42
Наши языки программирования жестко закодированы, чтобы знать, как обращаться с этим обозначением для чисел.
Что нашиэквивалент для проверки нуля?Мы знаем это.
(= n 0) ;; or (zero? n)
Каков наш эквивалент для проверки NonZero?Легко!
(> n 0)
Каковы наши эквиваленты для NonZero-q и NonZero-r?
(quotient n 10)
(remainder n 10)
Тогда мы можем в значительной степени подключиться и играть, чтобы получить форму рекурсивногофункции, которые имеют дело позиционно со своими числовыми входами.
(define (a-decimal-eating-function-template n)
(cond [(= n 0)
...]
[(> n 0)
... (a-decimal-eating-function-template (quotient n 10))
... (remainder n 10)]))
Выглядит знакомо?:)
Подробнее об этом см. Учебник, подобный Как разрабатывать программы .