我开始学习ocaml,并且真正体会到了递归在语言中的威力。然而,我担心的一件事是堆栈溢出。
如果ocaml使用堆栈进行函数调用,它最终不会溢出堆栈吗?例如,如果我有以下函数:
let rec sum x =
if x > 1 then f(x - 1) + x
else x;;
它最终一定会导致堆栈溢出。如果我在c++中做同样的事情(使用递归),我知道它会溢出。
所以我的问题是,有没有内置的保护措施来防止函数式语言溢出堆栈?如果不是,它们是不是像这样不太有用,因为上面的求和算法是用for循环的过程化风格编写的,可以处理任何数字(与整数溢出无关)?
我有以下语法,我需要将它转换为LL(1)语法
G = (N; T; P; S) N = {S,A,B,C} T = {a, b, c, d}
P = {
S -> CbSb | adB | bc
A -> BdA | b
B -> aCd | ë
C -> Cca | bA | a
}
关键是,我知道当这只是一部作品时如何转换,但我在互联网上找不到任何明确的方法来解决这个问题。
提前感谢!
哪种方法在现实世界中最流行:递归还是迭代?
例如,具有递归的简单树前置遍历:
void preorderTraversal( Node root ){
if( root == null ) return;
root.printValue();
preorderTraversal( root.getLeft() );
preorderTraversal( root.getRight() );
}
对于迭代(使用堆栈):
Push the root node on the stack
While the stack is not empty
Pop a no
我用Python写了下面的两个函数:
def recur_tet(b, n):
if n == 1:
return(b)
else:
return(b ** recur_tet(b, n - 1))
def iter_tet(b, n):
ans = 1
for i in range(n):
ans = b ** ans
return(ans)
而且,令人惊讶的是,递归版本的速度要快一些:
python3> %timeit recur_tet(2,4)
1 µs ± 12.5 ns per loop
我必须计算以下语法的第一组和第二组:
A -> B C
B -> A x | x
C -> y C | y
根据我的理解,我得到了以下计算:
首先,我们删除左递归。
A -> B C
B -> x B'
B' -> C x B' | ε
C -> y C | y
Follow (A) = {$}
但在书中,Follow (A) = {x,$}的答案
为什么?他们没有删除左递归吗?
我试图理解延续传递风格的转换。
我试图构建一个方案到C编译器,我想使用延续传递风格。是否继续传递方式是正确的做法,你们能解释我的转换规则吗?
例如,以下是Gambit方案的创建者Marc的一个。
我将总结他给出的延续传递风格规则,但请注意:我不理解它们。特别是我不明白什么是C。
这是一个符号:
[E]
C
表示连续C中表达式E的连续传递样式转换。
例如,有一个转换规则是这样的:
[c]
C
==>
(C c) ;; application of C to c
表示连续C中常数c的CPS转换。
什么是C?我很难理解C是什么。就像魔法一样。
另一条规则是:
[(if E1 E2 E3)