我最近一直在阅读关于Erlang的内容,以及由于使用迭代循环的困难,尾部递归如此频繁使用.
递归的这种高使用是否会降低它的速度,所有函数调用以及它们对堆栈的影响是什么？或者尾部递归否定了大部分内容？
类型值如何:
type Tree =
| Node of int * Tree list
有一个值引用自己以功能方式生成的值吗？
对于Tree的合适定义,结果值应该等于以下Python代码中的x:
x = Tree()
x.tlist = [x]
编辑:显然需要更多解释.我正在尝试学习F#和函数式编程,所以我选择实现之前用其他语言编写的封面树.这里相关的是每个级别的点是下面级别的点的子集.结构在概念上达到了水平 - 无限.
在命令式语言中,节点具有包含其自身的子列表.我知道这可以在F#中强制执行.不,它不会在封面树算法的情况下创建无限循环.
我记得应该总是避免在Java中使用递归方法调用.我认为原因是,通过在堆上保存调用的方法而产生的开销不值得在实现中减少代码行.
但是,最近有人告诉我,如果递归实现很好地捕获了问题空间,那就不是这样了.我没有完全理解这一点,因为每个递归方法都可以迭代实现,例如通过使用堆栈.
有几个问题可以通过使用递归实现来解决,例如遍历树数据结构.
如果一个总是避免重复实现 Java或不？如果不是,那么决定使用递归或迭代实现的好标准是什么.生产的开销是重要的还是优化的？我已经阅读了stackoverflow,Java中不支持尾递归优化.
例如,由于以下函数没有累加器,它是否仍然是尾递归的？
belong:: (Ord a) => a -> [a] -> Bool
belong a [] = False
belong a (h:t)
| a == h = True
| otherwise = belong a t
在递归调用之前处理函数中的所有计算,它是否被认为是尾递归的充分条件？
我在理解Common Lisp函数的性能时遇到了问题(我仍然是新手).我有这个函数的两个版本,它只是计算所有整数的总和n.
非尾递归版:
(defun addup3 (n)
(if (= n 0)
0
(+ n (addup (- n 1)))))
尾递归版:
(defun addup2 (n)
(labels ((f (acc k)
(if (= k 0)
acc
(f (+ acc k) (- k 1)))))
(f 0 n)))
我试图在输入CLISP中运行这些函数n = 1000000.这是结果
[2]> (addup3 1000000)
500000500000
[3]> (addup2 1000000)
*** - Program stack overflow. RESET
我可以在SBCL中成功运行,但非尾递归的更快(只有一点点,但这对我来说似乎很奇怪).我已经搜索了Stackoverflow问题的答案,但找不到类似的东西.为什么我的堆栈溢出虽然尾递归函数被设计为不将所有递归函数调用放在堆栈上？我是否必须告诉解释器/编译器优化尾调用？(我读过类似(proclaim '(optimize (debug 1))设置调试级别并以追踪能力为代价进行优化的内容,但我不知道这是做什么的).也许答案是显而易见的,代码是胡说八道,但我无法弄清楚.感谢帮助.
编辑:danlei指出了拼写错误,它应该是addup3在第一个函数中调用,所以它是递归的.如果纠正,两个版本都会溢出,但不是他的版本
(defun addup (n)
"Adds up the first N integers"
(do ((i …我正在尝试使用Windows服务调试生产问题,一旦多个并发连接处于活动状态,该服务就会迅速崩溃.通过核心转储和DebugDiag的神奇之处,我发现有一个挂起的GC操作,直到几个Preemptive GC禁用的线程完成了他们的工作才能启动.
以下是来自WinDbg的示例线程转储,显示了有问题的线程:
26 6e 1444 00..440 8009222 Disabled 00..200:00..f88 00..7a0 0 MTA (Threadpool Completion Port)
27 c1 1a0c 00..fe0 8009222 Disabled 00..e90:00..f88 00..7a0 0 MTA (Threadpool Completion Port)
28 b5 17bc 00..6f0 8009222 Disabled 00..268:00..f88 00..7a0 0 MTA (Threadpool Completion Port)
29 89 1f1c 00..ab0 8009222 Disabled 00..a30:00..f88 00..7a0 0 MTA (Threadpool Completion Port)
30 ac 2340 00..f70 8009220 Disabled 00..d00:00..d08 00..7a0 1 MTA (GC) (Threadpool Completion Port)
31 88 1b64 00..fd0 8009220 Enabled 00..b28:00..b48 00..7a0 0 MTA (Threadpool …我在F#中使用定点组合器时遇到问题:
let rec fix f a = f (fix f) a
fix (fun body num ->
if num = 1000000
then System.Console.WriteLine "Done!"
else body (num + 1)
) 0
(此代码仅用于演示问题,它是专门编写的,因此生成的IL代码易于阅读.)
此代码 - 在使用优化和尾调功能进行编译时 - 会导致a StackOverflowException.我查看了IL代码,可以将问题跟踪到调用内的lambda fix:
.method assembly static void f@1 (class FSharpFunc`2<int32, class Unit> body,int32 num)
{
ldarg.1
ldc.i4 1000000
bne.un.s IL_0014
ldstr "Done!"
call void Console::WriteLine(string)
ret
IL_0014: ldarg.0 // Load the 'body' function onto the stack.
ldarg.1 // Load num onto the stack. …f# tail-recursion tail-call-optimization f#-3.1 fixpoint-combinators
假设我写这样的代码:
tailrec fun odd(n: Int): Boolean =
if (n == 0) false
else even(n - 1)
tailrec fun even(n: Int): Boolean =
if (n == 0) true
else odd(n - 1)
fun main(args:Array<String>) {
// :( java.lang.StackOverflowError
System.out.println(even(99999))
}
如何让Kotlin优化这些相互递归的函数,以便我可以在main不抛出StackOverflowError的情况下运行？该tailrec关键字适用于单函数递归,但没有更复杂的.我还看到一个警告,即在使用tailrec关键字的地方没有找到尾调用.也许这对编译器来说太难了？
Integer>>#factorialPharo 的实施是:
factorial
"Answer the factorial of the receiver."
self = 0 ifTrue: [^ 1].
self > 0 ifTrue: [^ self * (self - 1) factorial].
self error: 'Not valid for negative integers'
这是一个尾递归定义.但是,我可以10000 factorial在工作区中无错误地进行评估.
Pharo是否在任何情况下执行尾调用优化,是否正在进行其他优化,还是只使用非常深的堆栈？
我的编程语言编译为C,我想实现尾递归优化.这里的问题是如何将控制传递给另一个函数而不从当前函数"返回".
如果控件传递给同一个函数,这很容易:
void f() {
__begin:
do something here...
goto __begin; // "call" itself
}
正如您所看到的,没有返回值和参数,这些参数在一个由全局变量处理的单独堆栈中传递.
另一种选择是使用内联汇编:
#ifdef __clang__
#define tail_call(func_name) asm("jmp " func_name " + 8");
#else
#define tail_call(func_name) asm("jmp " func_name " + 4");
#endif
void f() {
__begin:
do something here...
tail_call(f); // "call" itself
}
这类似于goto但是当goto将控制传递给函数中的第一个语句时,跳过编译器生成的"入口代码" jmp是不同的,它的参数是一个函数指针,你需要添加4或8个字节来跳过进入代码.
上述两者都可以工作,但前提是被调用者和调用者对由被调用者的入口代码分配的局部变量使用相同数量的堆栈.
我想leave用内联汇编手动,然后替换堆栈上的返回地址,然后执行legal函数调用f().但我的所有尝试都崩溃了.你需要修改BP并SP以某种方式.
那么再次,如何为x64实现这一点？(再次,假设函数没有参数并返回void).没有内联装配的便携式方式更好,但是接受装配.也许longjump可以用？
也许你甚至可以在堆栈上推送被叫地址,替换原来的返回地址而已ret？