Racket 中的生成递归和结构递归有什么区别?
最佳答案
当“子问题”与可能的数据片段完全匹配时,就会发生结构递归。
例如,处理列表lox
。最简单的情况是当 lox
为空时。否则,第一个子问题是处理(first lox)
,第二个子问题是处理(rest lox)
。您可以通过调用辅助函数来解决每个子问题,然后组合解决方案。
(define (process-list-of-x lox)
(cond
;; trivial case
[(empty? lox) ...]
[(cons? lox)
; combine the solutions
(...
; solve the first sub-problem
(process-x (first lox)) ; data-def tells you what the first sub-problem is
...
; solve the second sub-problem
(process-list-of-x (rest lox)) ; data-def tells you what the second sub-problem is
...)]))
不同的是,结构递归告诉您子问题是什么,而在生成递归中,子问题可以是任何东西。你经常需要一个新的想法来打破它。针对问题而非数据的 Eureka 时刻。
(define (solve-problem prob)
(cond
;; trivial case
[(trival-problem? prob) (... prob ...)]
[else
; combine the solutions
(...
; solve the first sub-problem
(solve-problem (generate-first-sub-problem prob)) ; you have to figure this out
...
; solve the second sub-problem
(solve-problem (generate-second-sub-problem prob)) ; data-def doesn't tell you how
...)]))
此外,结构递归保证它终止,因为子问题来自于分解数据。在生成递归中,子问题可能更复杂,因此您需要一些其他方法来确定它是否终止。
关于recursion - 生成递归和结构递归有什么区别?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47448045/