我最近学习了Haskell,并试图在可能的情况下将纯函数式传递给我的其他代码.这方面的一个重要方面是将所有变量视为不可变,即常量.为了做到这一点,许多将使用命令式循环实现的计算必须使用递归来执行,这通常由于为每个函数调用分配新的堆栈帧而导致存储器损失.在尾调用的特殊情况下(其中被调用函数的返回值立即返回给被调用者的调用者),然而,这种惩罚可以被称为尾调用优化的过程绕过(在一种方法中,这可以通过在正确设置堆栈后,基本上用jmp替换一个调用).MATLAB默认执行TCO,还是有办法告诉它？
matlab functional-programming tail-recursion tail-call-optimization
为了设置一些上下文,我正在学习Clojure,并且更普遍地学习Lisp.在我的Lisp之路上,我目前正在研究"Little"系列,以巩固功能编程和基于递归的解决方案的基础.在"The Little Schemer"中,我已经完成了许多练习,但是,我正在努力将其中的一些转换为Clojure.更具体地说,我正在努力将它们转换为使用"recur"以便启用TCO.例如,这里是一个基于Clojure的实现,来自"发生*"函数(来自Little Schemer),它计算出在S表达式列表中出现的原子的出现次数:
(defn atom? [l]
(not (list? l)))
(defn occurs [a lst]
(cond
(empty? lst) 0
(atom? (first lst))
(cond
(= a (first lst)) (inc (occurs a (rest lst)))
true (occurs a (rest lst)))
true (+ (occurs a (first lst))
(occurs a (rest lst)))))
基本上,(occurs 'abc '(abc (def abc) (abc (abc def) (def (((((abc)))))))))将评估为5.显而易见的问题是,如果给出一个S表达式列表太深,这个定义会消耗堆栈帧并且会破坏堆栈.
现在,我理解重构递归函数的选项,以使用累加器参数来启用将递归调用放入尾部位置(以允许TCO),但是如果此选项甚至适用于此类情况,我也在苦苦挣扎.
如果我尝试使用"recur"和使用累加器参数来重构这个,那么这里有多远:
(defn recur-occurs [a lst]
(letfn [(myoccurs [a lst count]
(cond
(empty? lst) 0
(atom? (first lst))
(cond
(= a (first …我正在通过"现在学习Prolog"在线书籍来获取乐趣.
我正在尝试编写一个谓词,该谓词遍历列表的每个成员并使用累加器向其中添加一个谓词.我已经很容易做到了,没有尾递归.
addone([],[]).
addone([X|Xs],[Y|Ys]) :- Y is X+1, addone(Xs,Ys).
但我已经读过,出于性能原因,最好避免这种类型的递归.这是真的？总是使用尾递归被认为是"好习惯"吗？是否值得努力使用累加器来养成良好的习惯？
我试图将此示例更改为使用累加器,但它会反转列表.我怎么能避免这个？
accAddOne([X|Xs],Acc,Result) :- Xnew is X+1, accAddOne(Xs,[Xnew|Acc],Result).
accAddOne([],A,A).
addone(List,Result) :- accAddOne(List,[],Result).
我最近一直在重写许多OCaml标准库函数,以便进行尾递归.鉴于这需要直接进行CPS转换,我仍然不知道为什么默认版本不是这样编写的.
例如,在标准库中,map定义为:
let rec map f = function
[] -> []
| a::l -> let r = f a in r :: map f l
我把它重写为:
let map f l =
let rec aux l k = match l with
[] -> k []
| a::l -> aux l (fun rest -> k (f a :: rest))
in aux l (fun x -> x)
Lua声称它正确实现尾调用,因此不需要为每个调用维护堆栈,因此允许无限递归,我试图写一个求和函数,一个不是尾调用,一个是尾调用:
非tailcall版本
function sum(n)
if n > 0 then
return n + sum(n-1)
end
end
print(sum(1000000))
stackoverflow正如预期的那样.
tailcall版本
function sum2(accu, n)
if n > 0 then
accu.value = accu.value + n
sum2(accu, n-1)
end
end
local accu = {value = 0}
sum2(accu, 1000000)
print(accu.value)
我想在这种情况下不存在stackoverflow,因为它是一个tailcall,但由于stackoverflow它仍然失败:
/bin/lua/5.1.4/bin/lua: tailcall.lua:13: stack overflow
stack traceback:
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function 'sum2'
tailcall.lua:13: in function …为了理解贪婪方法和动态编程等高级算法概念,首先需要精通递归.
我对递归比较新.每当提出问题时,首先要记住的是使用迭代的解决方案.即使我知道递归方法的含义及其工作方式,但很难以递归方式进行思考.
请回答以下问题,以帮助解决问题:
1)任何迭代方法都可以用递归代替,反之亦然吗？
例如,如何以递归方式打印大小为n的数组中的元素？
for i 0 to n
Print a[i]
2)如何递归地解决问题？步骤是什么？是否有任何提示可以确定问题可以递归解决？
例如:如果要求打印出字符串的所有子字符串
INPUT: CAT
OUTPUT: CAT,CA,A,AT,T
我可以快速提出迭代方法.使用两个循环可以解决问题.
但递归地如何解决它.如何识别问题可以递归解决.
如果回答我的第一个问题是肯定的,使用两次递归而不是迭代可以解决我的问题？
3)任何人都可以建议我一些材料/资源来彻底理解递归的概念吗？
基于丰富的stackoverflow,我一直在研究是否对特定的c#代码进行了尾递归优化.一些问题似乎在讨论
从C#4.0(Visual Studio 2013/2015)开始,如果可以确保尾递归优化,如何确保尾递归优化呢？
以下C#函数:
T ResultOfFunc<T>(Func<T> f)
{
return f();
}
毫不奇怪地汇编到这个:
IL_0000: ldarg.1
IL_0001: callvirt 05 00 00 0A
IL_0006: ret
但是等效的F#功能:
let resultOfFunc func = func()
汇编到这个:
IL_0000: nop
IL_0001: ldarg.0
IL_0002: ldnull
IL_0003: tail.
IL_0005: callvirt 04 00 00 0A
IL_000A: ret
(两者都处于发布模式).开头有一个额外的小窍门,我并不太好奇,但有趣的是附加ldnull和tail.说明.
我的猜测(可能是错误的)是ldnull必要的,如果函数是void这样,它仍然返回something(unit),但这并不能解释tail.指令的目的是什么.如果函数确实在栈上推送了某些东西会发生什么呢？是不是它会被一个不会弹出的额外null所困？
我正在学习F#(一般来说是功能编程的新手,虽然多年来使用C#的功能方面,但让我们面对它,这是非常不同的)我读过的一件事是F#编译器识别尾递归并编译它进入一个while循环(参见http://thevalerios.net/matt/2009/01/recursion-in-f-and-the-tail-recursion-police/).
我不明白的是,为什么你会写一个递归函数而不是一个while循环,如果那就是它将会变成什么.特别是考虑到你需要做一些额外的工作来使你的函数递归.
我有一种感觉,有人可能会说while循环不是特别功能,你想要所有功能和诸如此类的东西,所以你使用递归,但那么为什么编译器将它变成while循环就足够了？
谁可以给我解释一下这个？
假设我已经在Haskell中编写了一个函数，并且想断言它是尾递归的，并且编译器会对其进行优化。有办法吗？
我知道有一种方法可以在Scala中使用@tailrec注释。
import scala.annotation.tailrec
class Factorial2 {
def factorial(n: Int): Int = {
@tailrec def factorialAcc(acc: Int, n: Int): Int = {
if (n <= 1) acc
else factorialAcc(n * acc, n - 1)
}
factorialAcc(1, n)
}
}