Scheme 中的尾递归函数

2023-11-24

我正在准备圣诞节考试并做一些考试样本,我遇到了这个让我有点困惑的问题

Question

我可以很好地执行常规递归,但我无法理解如何使用尾递归编写相同的内容。

普通版:

    (define (factorial X)
      (cond
            ((eqv? X 1) 1)
            ((number? X)(* X (factorial (- X 1))))))

对于尾递归函数,函数返回后除了返回其值之外必须没有任何事情可做。也就是说,递归步骤中发生的最后一件事是对函数本身的调用。这通常是通过使用累加器参数来跟踪答案来实现的:

(define (factorial x acc)
  (if (zero? x)
      acc
      (factorial (sub1 x) (* x acc))))

上述过程最初将被调用1作为累加器,如下所示:

(factorial 10 1)
=> 3628800

请注意,当达到基本情况时,会返回累积值,并且acc参数在递归调用中的每个点都会更新。我必须向该过程添加一个额外的参数,但这可以通过定义内部过程或命名的过程来避免let, 例如:

(define (factorial x)
  (let loop ((x x)
             (acc 1))
    (if (zero? x)
        acc
        (loop (sub1 x) (* x acc)))))
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

Scheme 中的尾递归函数 的相关文章

  • 递归方法比交互式方法慢 10 倍 [关闭]

    这个问题不太可能对任何未来的访客有帮助 它只与一个较小的地理区域 一个特定的时间点或一个非常狭窄的情况相关 通常不适用于全世界的互联网受众 为了帮助使这个问题更广泛地适用 访问帮助中心 help reopen questions 代码已尽可
  • Karasuba算法递归过多

    我正在尝试用 c 实现 Karasuba 乘法算法 但现在我只是想让它在 python 中工作 这是我的代码 def mult x y b m if max x y lt b return x y bm pow b m x0 x bm x1
  • 在Racket中将结构递归转化为累积递归

    我有一些代码来查找最大高度并将其替换为关联的名称 身高和姓名有单独的列表 每个列表的长度相同且非空 我可以使用结构递归来解决这个问题 但必须将其更改为累积递归 而且我不确定如何做到这一点 我见过的所有例子都让我困惑 有人能够将代码变成使用累
  • 使用一次递归调用实现递归

    给定一个函数如下 f n f n 1 f n 3 f n 4 f 0 1 f 1 2 f 2 3 f 3 4 我知道使用递归来实现它 并在一个函数内进行三个递归调用 但我想在函数内仅使用一次递归调用来完成此操作 怎样才能做到呢 要实现使用
  • 在堆栈已满并给出分段错误之前,C/C++ 中的最大递归函数调用次数?

    我正在做一个问题 我使用递归函数来创建线段树 对于较大的值 它开始出现分段错误 所以我之前认为可能是因为数组索引值越界 但后来我认为这可能是因为程序堆栈太大 我编写这段代码是为了计算系统出现段错误之前允许的最大递归调用次数 include
  • Haskell 中的尾递归字符串分割

    我正在考虑分割字符串的问题s在一个字符处c 这表示为 break c s 其中 Haskell 库定义break c 足够接近 br br s h t if c h then s else let h t br t in h h t 假设我
  • 迭代函数可以调用自身吗?

    当观看下面的 MIT 6 001 课程视频时 讲师在 28 00 将此算法标记为迭代 但是 在 30 27 他说这个算法和实际的 递归 算法都是递归的 该函数正在使用基本情况调用自身 那么这次迭代情况如何 private int itera
  • 如何在递归调用函数时阻止 bash 创建子 shell

    这是一个计算阶乘的简单 shell 函数 bin bash function factorial if 1 lt 2 then echo 1 else echo 1 factorial 1 1 fi factorial 1 但我发现这个脚本
  • 通往楼梯顶部的可能路径

    这是一个非常经典的问题 我听说谷歌在他们的面试中使用过这个问题 问题 制定一个递归方法 打印从楼梯底部到楼梯顶部的所有可能的独特路径 有 n 个楼梯 您一次只能走 1 步或 2 步 示例输出 如果它是一个有 3 级楼梯的楼梯 1 1 1 2
  • C# 中的递归自定义配置

    我正在尝试创建一个遵循以下递归结构的自定义配置部分
  • @tailrec为什么这个方法不编译为“包含不在尾部位置的递归调用”?

    tailrec private def loop V key String V key match case gt loop key 此方法无法编译并抱怨它 包含不在尾部位置的递归调用 有人可以向我解释一下发生了什么事吗 这个错误消息对我来
  • 来自 JSON 的 Angular 8 动态表单

    我正在尝试从 JSON 模式递归生成动态表单 但我正在努力解决找不到表单控件的问题 这是代码示例 我收到这个错误 错误错误 找不到名称为 createdAt 的控件 我尝试了不同的方法 但仍然存在问题 我知道我错过了一些东西 所以请帮忙 任
  • 函数速度测试的奇怪结果

    我编写了一个使用递归来查找最大公因数 分母 的函数 gt gcd function a b if length a length b gt 1 warning Only scalars allowed using first element
  • 通过递归扩展 Prolog 目标?

    我 最终 实现了一些目标 这些目标将根据开始由 开始之后 and duration 然而 计划目标仅接受规定数量的任务 我想扩展计划目标的功能以接受单个列表并在计划时迭代该列表 不幸的是 我认为这将需要与can run and 冲突目标如下
  • 在 Pari-GP 中嵌套特定递归

    每个人 我最初在 Stackexchange 上发布了类似的问题 它已移至此处 可以在链接中找到 在 Matlab 中声明函数递归序列 https stackoverflow com questions 67146061 declaring
  • Scheme (Lisp) 中树的深度反转

    我对Scheme中的基本树数据结构进行了深度逆向 define deep reverse t cond null t not pair t t else cons deep reverse cdr t deep reverse car t
  • 如何在mit-scheme中正确使用(读取)?

    我在文档和 Rosetta 代码中读到 read 用于从控制台获取输入 所以我写了这段代码来检查这一点 display read 1 但 mit scheme 从不要求用户输入 程序就会终止 为什么会这样呢 在 REPL 中 display
  • 如何在C中递归地找到另一个字符串中的字符串位置?

    我们有一个任务来创建带有两个字符串参数的递归函数 原型应该是这样的 int instring char word char sentence 如果我们愿意调用函数 instring Word Another Word 它应该具有以下返回值
  • 了解 F# 尾递归

    最近在学习F 我尝试以不同的方式解决问题 像这样 0 1 2 3 4 5 6 7 8 gt 0 1 2 3 4 5 6 7 8 head recursive let rec toTriplet v1 list match list with
  • Python脚本递归重命名文件夹和子文件夹中的所有文件

    您好 我有许多不同的文件需要重命名为其他文件 我已经走到这一步了 但我想要拥有它 这样我就可以有许多要替换的项目及其相应的替换项 而不是逐一输入 运行代码然后再次重新输入 更新 另外 我需要重命名以仅更改文件的一部分而不是整个文件 因此如果

随机推荐