So our class was given an assignment to convert decimal numbers to their octal representations. I managed to just tinker with it till it worked, but I'm having some problems comprehending why it works. Any possibility at explaining the recursion in a more simplistic manner? Thanks.
(define octify
(lambda (n)
(cond
((zero? n) 0)
((zero? (quotient n 8)) n)
(else (+ (* 10 (octify (quotient n 8))) (remainder n 8))))))
On
The mainstream representation of number, the one that took the world by storm, is positional notation. It's a representation that's tied intimately with the concept of quotient and remainder operations, which you're seeing somewhat from your recursive function defintion. Why is that?
Let's take a quick aside: positional notation is not the only viable representation for number. One way that comes up every so often is a tallying approach, where a number is either zero or one more than a number. We can use sticks. Since we're talking about programs, let's use a data-type.
Number :== Zero
| Successor(n) where n is a number
Read this as "A number is either Zero, or the successor of another number". Or, to code it up in a Scheme that supports structured representations (like Racket), we can write this:
(define-struct Zero ())
(define-struct Successor (n))
For example, representing three with this notation would be (Successor (Successor (Successor (Zero))). (This representation is called Peano, if I'm remembering right.)
Functions that deal with this kind of structured datatype often have the same shape as that of the datatype itself. That is, a function that works on a representation in Peano will look something like this:
;; 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))
...]
where the ... will be something specific to the particular problem you're trying to solve on Peano numbers. It's a matter of functions following the structure of the data that they're working on. As an concrete example of a Peano-eating function, here's one that turns a piano into a bunch of stars:
;; 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)))]))
Anyway, so datatypes lead naturally to functions with particular shapes. This leads us to going back to positional notation. Can we capture positional notation as a datatype?
It turns out that we can! Positional notation, such as decimal notation, can be described in a way similar to how the Peano number description worked. Let's call this representation Base10, where it looks like this:
Base10 :== Zero
| NonZero(q, r) where q is a Base10, and r is a digit.
Digit :== ZeroD | OneD | TwoD | ... | NineD
And if we want to get concrete in terms of programming in a language with structures,
(define-struct Zero ())
(define-struct NonZero(q r))
(define-struct ZeroD ())
(define-struct OneD ())
(define-struct TwoD ())
(define-struct ThreeD ())
(define-struct FourD ())
;; ...
For example, the number forty-two can be represented in Base10 as:
(NonZero (NonZero (Zero) (FourD)) (TwoD))
Yikes. That looks a bit... insane. But let's lean on this a little more. As before, functions that deal with Base10 will often have a shape that matches Base10's structure:
;; 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)]))
That is, we can get the shape of a recursive function that works on Base10 pretty much for free, just by following the structure of Base10 itself.
... But this is a crazy way to deal with numbers, right? Well... remember that wacky representation for forty-two:
(NonZero (NonZero (Zero) (FourD)) (TwoD))
Here's another way to represent the same number.
((0 * 10 + 4) * 10 + 2)
Pretty much the same idea. Here, let's get rid of a few more parentheses. We can represent forty-two with the following notation:
42
Our programming languages are hardcoded to know how to deal with this notation for numbers.
What's our equivalent for checking Zero? We know that one.
(= n 0) ;; or (zero? n)
What's our equivalent for checking NonZero? Easy!
(> n 0)
What are our equivalents for NonZero-q and NonZero-r?
(quotient n 10)
(remainder n 10)
Then, we can pretty much plug-and-play to get the shape of recursive functions that deal positionally with their numeric inputs.
(define (a-decimal-eating-function-template n)
(cond [(= n 0)
...]
[(> n 0)
... (a-decimal-eating-function-template (quotient n 10))
... (remainder n 10)]))
Look familiar? :)
For more of this, see a textbook like How to Design Programs.
On
Obviously, (octify 0) should be 0 and (octify n) for n such that 0 < n < 8 is n. The next condition is the complex one. The first question is "what does (octify (quotient n 8)) return?". With base-10 numbers, dividing by 10 removes the right-most digit - 145/10=14 (assuming integer division). With base-8 numbers, dividing by 8 works similarly. Therefore, (octify (quotient n 8)) returns a number with all but the last digit of n, assuming that octify is defined correctly (which we have to assume). Now, we need to take this number and "push" it a digit to the left. Multiplying it by 10 does this, since the printer will be printing it in base-10. (remainder n 8) gets the final digit of n. Now we have the first however many digits (with a zero for the final digit to go) and the final digit, so we can combine them by adding them. At this point, the function is done and the correct value is returned.
First of all, a "number" is not decimal or octal. A "number" is a mathematical concept, which is stored in the computer in some sort of format with a bunch of bits. Decimal and octal refer to different string representations of a number. That is, "decimal" and "octal", etc. only make sense when talking about strings, and a particular number can be converted into a string as decimal or octal or whatever.
Producing the octal (or some other base) string representation of an integer is a common basic task in programming. The algorithm you have basically figured out: take the remainder of the number by the base to get the last digit, then recurse on the quotient of the number by the base to get the rest (all but last digit) of the number.
What is strange about what you are doing is that you are not producing a string, as one would normally do for this task. Instead, you are trying to pack it back into a number, in such a way that the resulting number's decimal representation would look like what the octal representation of the original number would look like. (This happens to be possible since any octal representation is also a valid decimal representation of some number. This wouldn't be possible with hex, for example.) In other words, you are converting a number to its octal string representation, then parsing that string into a number as if it were a decimal representation. For example, take the number 42, whose decimal representation is the string "42" and octal representation is the string "52". Your program returns the number 52 (whose octal representation is the string "64").
You may be confused because you are typing this into an interpreter, and when you compute or print a number, it outputs the decimal representation. But it is important to understand that a number is completely different from a string. (If you computed a string in your interpreter, perhaps it would surround it with quotes or something.) It would make most sense if your program outputted the string of the octal representation, rather than a number which when printed, looks like it.