所以我们的类被赋予一个转换十进制数到它们的八进制表示。我设法修补它,直到它工作,但我有一些问题,理解它为什么工作。 任何可能以更简单的方式解释递归?谢谢。方案递归(十进制到八进制)
(define octify
(lambda (n)
(cond
((zero? n) 0)
((zero? (quotient n 8)) n)
(else (+ (* 10 (octify (quotient n 8))) (remainder n 8))))))
所以我们的类被赋予一个转换十进制数到它们的八进制表示。我设法修补它,直到它工作,但我有一些问题,理解它为什么工作。 任何可能以更简单的方式解释递归?谢谢。方案递归(十进制到八进制)
(define octify
(lambda (n)
(cond
((zero? n) 0)
((zero? (quotient n 8)) n)
(else (+ (* 10 (octify (quotient n 8))) (remainder n 8))))))
首先,“一把手”是不是十进制或八进制。 “数字”是一个数学概念,它以某种格式存储在计算机中,并带有一堆位。十进制和八进制表示数字的不同字符串表示形式。也就是说,“十进制”和“八进制”等只有在谈到字符串时才有意义,并且可以将一个特定的数字转换为十进制或八进制或其他形式的字符串。
生成一个整数的八进制(或其他基数)字符串表示是编程中常见的基本任务。你基本上已经算出的算法:以基数的剩余部分取得最后一位数字,然后递增基数的商数以获得数字的其余部分(除最后一位数字外)。
你在做什么的奇怪之处在于你没有生成一个字符串,正如通常为此任务所做的那样。相反,您试图将其打包回数字中,以便生成的数字的十进制表示看起来像原始数字的八进制表示形式。 (这是可能的,因为任何八进制表示也是某个数字的有效十进制表示,例如对于十六进制,这是不可能的)。换句话说,您正在将数字转换为其八进制字符串表示形式,然后解析将该字符串转换为数字,就像它是十进制表示形式一样。例如,采用数字42,其十进制表示形式是字符串“42”,八进制表示形式是字符串“52”。您的程序返回数字52(其八进制表示形式是字符串“64”)。
您可能会因为将此输入到解释器中而感到困惑,并且当您计算或打印一个数字时,它会输出十进制表示法。但是了解数字与字符串完全不同是很重要的。 (如果你在你的解释器中计算了一个字符串,也许它会用引号或其他东西包围它。)如果你的程序输出的是八进制表示的字符串,而不是在打印时看起来像它的数字,那将是最有意义的。
数字的主流表示形式,是风暴带走世界的数字,是positional notation。它是一个与商和剩余操作概念密切相关的表示,你从递归函数定义中可以看到它。这是为什么?让我们快速放一边:位置表示法不是数字的唯一可行表示形式。经常出现的一种方法是统计方法,其中数字是零或比数字多一个。我们可以使用棍棒。由于我们正在讨论程序,我们使用数据类型。
Number :== Zero
| Successor(n) where n is a number
阅读此为“一个数字是零,或另一个数字的后继者”。或者,它在支持结构化的表述(如球拍)一个方案代码,我们可以这样写:
(define-struct Zero())
(define-struct Successor (n))
例如,代表这种表示是(Successor (Successor (Successor (Zero)))
。 (如果我记得正确的话,这个表示法叫做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->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)))]))
无论如何,所以数据类型自然会导致与特定形状的功能。这导致我们回到位置表示法。我们可以捕获位置表示法作为数据类型吗?
事实证明,我们可以!位置表示法(如十进制表示法)可以用类似于Peano编号描述的方式描述。让我们称这种表示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))
让人惊讶。这看起来有点疯狂。但让我们再多关注一下。和以前一样,与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)
什么是我们的等价物检查非零?简单!
(> 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)]))
看起来很熟悉吗? :)
更多信息,请参阅How to Design Programs之类的教科书。
很明显,(octify 0)
应该是0和(octify n)
n代表0 < n < 8代表n。下一个条件是复杂的。第一个问题是“(octify (quotient n 8))
返回什么?”。以10为底的数字,除以10将删除最右边的数字 - 145/10 = 14(假设整数除法)。基数为8的数字,除以8的作用类似。因此,(octify (quotient n 8))
返回一个数字,除n的最后一位数字外,假设octify
已正确定义(我们必须假设)。现在,我们需要把这个数字“推”到左边一个数字。将其乘以10即可,因为打印机将以10为基础打印。 (remainder n 8)
得到n的最后一位。现在我们有第一个数字(最后一位数字为零)和最后一位数字,所以我们可以通过添加它们来组合它们。此时,函数完成并返回正确的值。