recursion - 如何在 Scheme/Racket 中使用尾递归实现附加过程?
问题描述
很长一段时间以来,我都在尝试使用尾递归(迭代)在 Racket 中实现附加过程。
到目前为止我做的最好的解决方案是:
(define (my-reverse lst)
(define (iter lst reversed)
(if (null? lst)
reversed
(iter (cdr lst) (cons (car lst) reversed))))
(iter lst '()))
(define (append-iter el lst)
(my-reverse (cons el (my-reverse lst))))
(append-iter 4 '(1 2 3)) ; (1 2 3 4)
我的问题是是否有更好的实施方式?
解决方案
好吧,这取决于您对“更好”的定义:)。您的解决方案很简单,并且您找不到更直接的方法来编写自己的过程以使用尾递归将元素附加到列表的末尾。
我唯一的评论是它my-reverse
与内置reverse
过程一样,它肯定是尾递归的,所以你可以简单地把它写成:
(define (append-iter el lst)
(reverse (cons el (reverse lst))))
如果您可以使用延续传递样式,则以下解决方案也是尾递归的,它仅取决于最基本的原始过程:
(define (append-iter el lst)
(append-cps lst (cons el '()) (lambda (x) x)))
(define (append-cps lst1 lst2 k)
(if (null? lst1)
(k lst2)
(append-cps
(cdr lst1)
lst2
(lambda (appended-cdr)
(k (cons (car lst1) appended-cdr))))))
无论哪种方式,它都按预期工作:
(append-iter 4 '(1 2 3))
=> '(1 2 3 4)
如果您很好奇,CPS 解决方案将评估为如下所示的表达式,这自然会导致答案:
((lambda (append-cdr)
((lambda (appended-cdr)
((lambda (appended-cdr)
((lambda (x) x)
(cons 1 appended-cdr)))
(cons 2 appended-cdr)))
(cons 3 append-cdr)))
'(4))
=> '(1 2 3 4)
推荐阅读
- laravel - 如何使用laravel从文件夹中删除mp3文件
- java - Java将字符串转换为日期问题
- forms - 字段选择选项给出无效选择错误
- css - django这不起作用..图像未显示在页面中
- firebase - 将 Quasar 应用程序部署到 Firebase 时出现空白页面
- mysql - 有多个键列时如何形成合并查询?
- python-3.x - 如何使用 tkinter.Label 更改文本颜色
- git - 我们可以在不克隆 repo 的情况下获得最后的提交消息吗?
- python - 使用 Python 请求登录 Intuit Qucikbooks
- java - 如何在Android中制作编码字符串?