标签: tail-recursion

我已将有问题的代码隔离到此函数(使用ASP.NET的Membership类):

let dbctx = DBSchema.GetDataContext()
let rec h1 (is2_ : int) (ie2_ : int) : unit =
    match is2_ >= ie2_ with
    | true ->
        let st2 = query {
            for row in dbctx.Tbl_Students do
            where (row.Id = is2_)
            head}
        let l2 =
            Membership.FindUsersByEmail (st2.Email_address)
            |> Seq.cast<_>
            |> Seq.length
        match l2 >= 1 with
        | true -> 
            ()
        | false ->
            Membership.CreateUser (st2.Email_address, password, st2.Email_address)
            |> ignore
        h1 (is2_ - 1) ie2_
    | false ->
        ()

System.OutOfMemoryException经过几次5626迭代后我才得到了 …

我正在读杰森的书，不太明白以下程序：

let fact2 i =
    let rec loop accum i =
        if i = 0 then 
            accum
        else
            loop (i * accum) (i - 1)
    in
        loop 1

1. 累加器是如何初始化的？
2. 最后两行（即在循环 1 中）的含义是什么？循环有两个参数。为什么这里只传递一个（即循环1）。

非常感谢！！！

出于某些特殊原因,我想在大程序中删除所有@tailrec的效果,但是不想手动执行,编译时是否有任何可选参数可以关闭尾递归优化？我想在代码中留下@tailrec,但是不想检查它并在编译时进行尾递归优化.那可能吗？

我在scala中有一个函数,我想知道是否有可能进入尾递归函数.

def get_f(f: Int => Int, x: Int, y: Int): Int = x match {
  case 0 => y
  case _ => f(get_f(f, x - 1, y))
}

我实际上在一个问题上坐了一个多小时，但没有\xc2\xb4找到解决方案。\n我有这个数据类型：\ntype \'a tree = Empty | Node of \'a * \'a tree * \'a tree

我必须找到一个函数来转换有序列表中给定的树。也不存在像左孩子必须小于右孩子这样的不变量。我已经找到了“正常”递归解决方案，但没有找到尾递归解决方案。我已经考虑过构建一个无序列表并使用 对其进行排序List.sort，但这使用了不是尾递归的合并排序。也许有人有一个好的建议。

谢谢你！

我有这个函数来功能性地遍历图形：

private def dfs(current: RCell, rCellsMovedWithEdges: Vector[RCell], acc: Vector[RCell] = Vector()): Vector[RCell] = {
    current.edges.foldLeft(acc) {
      (results, next) =>
        if (results.contains(rCellsMovedWithEdges(next))) results
        else dfs(rCellsMovedWithEdges(next), rCellsMovedWithEdges, results :+ current)
    } :+ current
  }

从 manuel kiessling 此处获得的实施

这很好，但我担心最后的“:+ current”会使其成为非尾递归。

我把它改成这样：

private def dfs(current: RCell, rCellsMovedWithEdges: Vector[RCell]): Vector[RCell] = {

    @annotation.tailrec
    def go(current: RCell, rCellsMovedWithEdges: Vector[RCell], acc: Vector[RCell] = Vector()): Vector[RCell] = {
      current.edges.foldLeft(acc) {
        (results, next) =>
          if (results.contains(rCellsMovedWithEdges(next))) results
          else go(rCellsMovedWithEdges(next), rCellsMovedWithEdges, results :+ current)
      }
    }
    go(current, rCellsMovedWithEdges) :+ …

我正在为代码2018（剧透警告）的到来问题解决方案，其中我需要一个函数，该函数接受一个字符串（或一个char list），并在它们反应时删除每对字符。本练习描述了两个字符或“聚合物”中的“元素”，当它们是相同字母但大小写不同时会发生反应。所以从开始AbBc会离开你Ac。请记住，在一个反应​​之后，两个字符可能会彼此并排出现，而不是在以前，并引起新的反应。

我以为我可以通过使用仅处理前两个字符并递归调用自身的递归函数来解决此问题，但是由于输入字符串很大，因此会导致stackoverflow exception：

let rec react polymer =
    match polymer with
    | [] -> []
    | [x] -> [x]
    | head::tail ->
        let left = head
        let right = List.head tail
        let rest =  List.tail tail
        // 'reacts' takes two chars and
        // returns 'true' when they react
        match reacts left right with
        // when reacts we go further with
        // the rest …

我正在尝试实现尾递归阶乘计算器，但仍然出现堆栈溢出。谁能帮我找出原因？

• 我读过 Java 8 支持尾调用优化，但我想我一定没有正确实现它。
• 我已经读到可以使用 lambda 表达式。我不确定我是否完全理解这个概念，但我仍在阅读。
• 我只是在寻找有关如何使用真正的尾调用优化、lambda 表达式或我可以使用的任何建议。

代码：

package factorielRecursiveTerminale;

import java.math.BigInteger;
import java.util.Scanner; 

public class factorielRecursiveTerminale {  
    
    public static BigInteger factoriel(BigInteger n, BigInteger m) {
        if (n.compareTo(BigInteger.ZERO) < 1) return m;             
        return factoriel(n.subtract(BigInteger.ONE), n.multiply(m));
    }                                                               
                                                                
    public static BigInteger fact(int n) {  //convertir l'entree en BigInteger et lancer la recursion
        if(n < 0) {
            return BigInteger.valueOf(-1);
        }
        BigInteger b = BigInteger.valueOf(n);
        return factoriel(b, BigInteger.ONE);
    }

    public static void runBigFact() {                       //gestion des erreurs + boucle d'entree de …

我正在 Kotlin 中练习递归，并在运行以下 2 个函数时得到了其他结果：

tailrec fun fac1(n: Long): BigInteger {
    if(n == 1L)
        return BigInteger.ONE
    else
        return n.toBigInteger() * fac1(n-1)
}
println("fac1(10000) = ${fac1(10000)}")

fac1(10000)的结果：Exception in thread "main" java.lang.StackOverflowError

tailrec fun fac2(n: Long, a: BigInteger = BigInteger.ONE): BigInteger {
    return if(n == 1L) a else fac2(n -1, a * n.toBigInteger())
}
println("fac2(10000) = ${fac2(10000)}")

fac2(10000) 可以执行并返回结果：fac2(10000) = 284625968091705451890.....

有人可以向我解释一下这两个函数之间的区别以及为什么函数 2 可以执行而函数 1 不能执行？

我正在解决OCaml 教程之一中发布的问题。其中之一是编写一个函数来计算列表的长度。它应该是尾递归的。

朴素的非尾递归解决方案是：

let rec length_naive xs  = (** Not tail recursive *)
  match xs with
  | [] -> 0
  | _ :: xs -> 1 + length_naive xs;;

(length_naive [@tailcall]) [1, 2, 3, 4];;

let one_hundred_million = 100000000;;
let non_tail_result = length_naive(List.init one_hundred_million (Fun.id));;
print_endline("Non-tail-recursive result: " ^ string_of_int(non_tail_result));;

编译和运行它完全按照预期工作。打印警告（由于@tailcall），并且由于堆栈溢出而执行失败：

$ ocamlc lib/so.ml
File "lib/so.ml", line 14, characters 0-39:
14 | (length_naive [@tailcall]) [1, 2, 3, 4];;
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 51 [wrong-tailcall-expectation]: expected tailcall

$ ./a.out …