我开始学习ocaml,我非常欣赏语言中递归的力量.但是,我担心的一件事是堆栈溢出.
如果ocaml使用堆栈进行函数调用,它最终是否会溢出堆栈？例如,如果我有以下功能:
let rec sum x =
if x > 1 then f(x - 1) + x
else x;;
它必须最终导致堆栈溢出.如果我在c ++(使用递归)中做相同的事情,我知道它会溢出.
所以我的问题是,是否有内置的安全措施来防止函数式语言溢出堆栈？如果不是这样,它们是不是没那么有用,因为上面的求和算法,用带有for循环的过程样式编写,可以处理任何数字(不相关的整数溢出)？
stack-overflow functional-programming imperative-programming tail-call-optimization
我在C#中看到了一些关于丢失尾部调用优化的问题,据说这种语言不适合递归算法实现.然而,这引出了一个问题,我们如何进行尾调用优化,并在引发异常时或者可以使用反射来检查调用堆栈并对其进行操作时仍提供合理的堆栈跟踪.
我已经阅读了一些关于Scheme中尾调优化的内容.但我不确定我是否理解尾调用的概念.如果我有这样的代码:
(define (fac n)
(if (= n 0)
1
(* n (fac (- n 1)))))
这可以优化,以便它不会占用堆栈内存吗？或者尾部调用优化只能应用于这样的函数:
(define (factorial n)
(let fact ([i n] [acc 1])
(if (zero? i)
acc
(fact (- i 1) (* acc i)))))
我正在研究scala TCO并编写了以下代码
import scala.annotation.tailrec
final def tailReccursionEx(str:String):List[String]={
@tailrec
def doTailRecursionEx(str:String,pos:Int,accu:List[String]):List[String]={
if(pos==str.length) return accu
else{
doTailRecursionEx(str,pos+1,accu++accu.foldLeft(List[String](str(`pos`).toString)){
(l,ch)=>l:+ch+str(`pos`)})
}
}
doTailRecursionEx(str,0,List[String]())
}
我已通过@tailrec测试,我相信我的函数是自递归尾调用.然而,当我查看java字节代码时
javap -c -private RecursionEx\$\$anonfun\$doTailRecursionEx\$1\$1
我看不到所承诺的转到了TCO自我递归函数.这是字节码.
public RecursionEx$$anonfun$doTailRecursionEx$1$1(java.lang.String, int);
Code:
0: aload_0
1: aload_1
2: putfield #35; //Field str$2:Ljava/lang/String;
5: aload_0
6: iload_2
7: putfield #41; //Field pos$1:I
10: aload_0
11: invokespecial #93; //Method scala/runtime/AbstractFunction2."<init>":()V
14: return
}
Ruby中的递归函数中是否存在Stack Overflow错误的解决方法？
比方说,我有这个块:
def countUpTo(current, final)
puts current
return nil if current == final
countUpTo(current+1, final)
end
如果我打电话countUpTo(1, 10000),我会收到一个错误:stack level too deep (SystemStackError).
它似乎在8187处突破.是否有一些函数我可以调用告诉Ruby忽略堆栈的大小,或者增加最大堆栈大小的方法？
据我所知,Clojure recur是由编译器支持的,而在其他lisps中它是在较低级别实现的.
在我读到的时候,这不是一般的"TCO".除了显而易见的(需要一个关键字+检查),它在recur哪些方面不那么强大？
使用SWI Prolog（Win x64）的开发版本，我为确定性词法分析器（托管在github上）写了DCG谓词（因此，所有外部谓词都没有选择点）：
read_token(parser(Grammar, Tables),
lexer(dfa-DFAIndex, last_accept-LastAccept, chars-Chars0),
Token) -->
( [Input],
{
dfa:current(Tables, DFAIndex, DFA),
char_and_code(Input, Char, Code),
dfa:find_edge(Tables, DFA, Code, TargetIndex)
}
-> { table:item(dfa_table, Tables, TargetIndex, TargetDFA),
dfa:accept(TargetDFA, Accept),
atom_concat(Chars0, Char, Chars),
NewState = lexer(dfa-TargetIndex,
last_accept-Accept,
chars-Chars)
},
read_token(parser(Grammar, Tables), NewState, Token)
; {
( LastAccept \= none
-> Token = LastAccept-Chars0
; ( ground(Input)
-> once(symbol:by_type_name(Tables, error, Index, _)),
try_restore_input(Input, FailedInput, InputR),
Input = [FailedInput | InputR],
format(atom(Error), '~w', [FailedInput]),
Token = Index-Error
; …除了尾递归之外,还有可能进行尾调用优化吗？我一直试图找到或想到一个不涉及递归的,但没有成功.可能吗？任何例子？
c c++ compiler-construction optimization tail-call-optimization
据说一些虚拟机,尤其是JVM,不支持TCO.因此,像Clojure这样的语言需要用户使用loop recur.
但是,我可以重写自尾调用以使用循环.例如,这是一个尾调用阶乘:
def factorial(x, accum):
if x == 1:
return accum
else:
return factorial(x - 1, accum * x)
这是一个等价的循环:
def factorial(x, accum):
while True:
if x == 1:
return accum
else:
x = x - 1
accum = accum * x
这可以通过编译器来完成(我编写了这样做的宏).对于相互递归,您可以简单地内联您正在调用的函数.
因此,鉴于您可以在不需要任何VM的情况下实现TCO,为什么不使用语言(例如Clojure,Armed Bear Common Lisp)呢？我错过了什么？
只是为了好玩(Project Euler#65)我想实现这个公式
n_k = a_k*n_k-1 + n_k-2
以有效的方式.a_k是1或者(* 2 (/ k 3)),取决于k.
我从一个递归的解决方案开始:
(defun numerator-of-convergence-for-e-rec (k)
"Returns the Nth numerator of convergence for Euler's number e."
(cond ((or (minusp k)) (zerop k) 0)
((= 1 k) 2)
((= 2 k) 3)
((zerop (mod k 3)) (+ (* 2 (/ k 3) (numerator-of-convergence-for-e-rec (1- k)))
(numerator-of-convergence-for-e-rec (- k 2))))
(t (+ (numerator-of-convergence-for-e-rec (1- k))
(numerator-of-convergence-for-e-rec (- k 2))))))
显然,它适用于小型k但速度很慢 …