标签: tail-recursion

让我们来看看Knight Tour问题吧.可以转换为迭代吗？困扰我的是回溯部分.如何在循环中回溯？当我从递归到迭代时,是否必须使用堆栈数据结构来实现回溯？

我在这里以更好的方式问了这个问题:有人能通过代码描述一个回溯迭代而不是递归的实际例子吗？

这是一个使用尾递归的lisp代码.

(defun factorial (f n)
    (if (= n 1)
        f
        (factorial (* f n) (- n 1))))

我把它翻译成clojure代码,期望相同的尾递归优化.

(defn fact [f n]
    (if (= n 1)
        f
        (fact (* f n) (dec n))))

但是我得到了这个整数溢出(不是堆栈溢出),即使是很小的数字,如(fact 1 30).

ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1374)

我尝试过recur,但得到了同样的错误.

(defn factorial [f n]
    (if (= n 1)
        f
        (recur (* f n) (dec n))))

clojure代码有什么问题？

像这样的简单追加函数(在F#中):

let rec app s t =
   match s with
      | [] -> t
      | (x::ss) -> x :: (app ss t)

当s变大时会崩溃,因为函数不是尾递归的.我注意到F#的标准追加功能不会因大列表而崩溃,因此必须以不同方式实现.所以我想知道:追尾的尾递归定义怎么样？我提出了这样的事情:

let rec comb s t =
   match s with
      | [] -> t
      | (x::ss) -> comb ss (x::t)
let app2 s t = comb (List.rev s) t 

哪个有效,但看起来很奇怪.是否有更优雅的定义？

我在clojure中有一个简单的素数计算器(一种效率低下的算法,但我现在只想了解recur的行为).代码是:

(defn divisible [x,y] (= 0 (mod x y)))

(defn naive-primes [primes candidates] 
  (if (seq candidates)
      (recur  (conj primes (first candidates)) 
              (remove (fn [x] (divisible x (first candidates))) candidates))
      primes)
)

只要我不想找到太多数字,这就有用.例如

(print (sort (naive-primes [] (range 2 2000))))

作品.对于任何需要更多递归的事情,我都会遇到溢出错误.

    (print (sort (naive-primes [] (range 2 20000))))

不管用.一般来说,我是否在没有尝试TCO的情况下再次使用复发或再次调用naive-primes似乎没有任何区别.为什么我在使用recur时遇到大型递归错误？

有没有人写过一篇正式的论文,描述了一种(自动)将函数转换为尾递归的方法？我正在寻找大学级的正式治疗方法,包括限制(可以转换的功能类型),转换程序,以及可能的正确性证明？Haskell中的例子将是一个奖励.

我正在从Conrad Barski的"Lisp之乡"一书中学习Lisp.现在我遇到了我的第一个绊脚石,作者说:

以这种方式调用自己不仅允许在Lisp中使用,而且经常受到强烈鼓励

在显示以下示例函数以计算列表中的项目之后:

(defun my-length (list)
  (if list
    (1+ (my-length (cdr list)))
    0))

当我my-length用包含一百万个项目的列表调用此函数时,我收到堆栈溢出错误.因此,无论你休想有一个列表,长期在Lisp的(所以也许我用例是没用的),或者还有另一种方法来计算在这么长的列表项.你能否对此有所启发？(顺便说一句,我在Windows上使用GNU CLISP).

我正在使用动态编程解决Haskell中的背包问题.我的第一次尝试是建立一个二维表.但是当输入很大时(例如100*3190802表),内存容易被炸毁.

知道任何给定的行i只依赖于行(i - 1),我改为编写一个函数,希望利用尾递归:

import Data.Vector (Vector, (!))
import qualified Data.Vector as V

-- n items, k capacity, vs values, ws weights
ans:: Int -> Int -> Vector Int -> Vector Int -> Int
ans n k vs ws =
    let row = initRow k vs ws
    in  row ! k

initRow :: Int -> Vector Int -> Vector Int -> Vector Int
initRow k vs ws = itbl 1 $ V.replicate (k + 1) 0 …

我正在我的人工智能实验室学习Prolog,从源头学习Prolog Now!.

在第5章中,我们来了解累加器.作为示例,给出了这两个代码片段. 查找列表的长度

没有累加器:

len([],0).
len([_|T],N) :- len(T,X), N is X+1.

与累加器:

accLen([_|T],A,L) :- Anew is A+1, accLen(T,Anew,L).
accLen([],A,A).

我无法理解,这两个片段在概念上有何不同？累加器到底有什么不同？有什么好处？

蓄能器听起来像中间变量.(如果我错了,请纠正我.)到目前为止,我已经在我的程序中使用过它们,所以它真的是一个很大的概念吗？

在这次演讲中,在前8分钟,Runar解释说Scala在消除尾部呼叫方面存在问题,这让我想知道F#是否有类似的问题？如果没有,为什么不呢？

这是我的功能:

let rec applyAll rules expr =
  rules
  |> List.fold (fun state rule ->
    match state with
    | Some e ->
      match applyRule rule e with
      | Some newE -> Some newE
      | None -> Some e
    | None -> applyRule rule expr) None
  |> Option.bind (applyAll rules)

它采用一组规则并应用它们,直到输入表达式尽可能减少.我可以重写它Option.bind是一个match表达式,它显然会利用尾部调用优化.但是,这对我来说更优雅,所以我希望保持原样,除非它不必要地消耗堆栈.F#是否使用此代码执行TCO？

编辑:此代码始终返回None; 我会解决这个问题,但我认为这个问题仍然有意义.