大师作文网λ(lamda)演算如何描述递归函数
来源：学生作业帮 编辑：大师作文网作业帮 分类：数学作业 时间：2024/11/20 15:07:04
λ(lamda)演算如何描述递归函数
都是Lamda演算是研究函数的工具,可是我弄不明白如何用lamda演算表示递归函数呢?
例如F(a,n)=n==1?a*2:F(F(a,n-1),1)
都是Lamda演算是研究函数的工具,可是我弄不明白如何用lamda演算表示递归函数呢?
例如F(a,n)=n==1?a*2:F(F(a,n-1),1)
自己照着这个例子改改就可以了.
递归是一种以函数自身迭代自身变元的算法,一般是通过函数自身来定义函数的方式实现.表面看来 lambda 演算不允许递归,其实这是一种对递归的误解.考虑阶乘函数 f(n) 一般这样递归地定义：
f(n) = 1,若 n = 0; n•f(n-1),若 n>0.
λ语言：
FACT = λ n.n (λ u.MULT n (FACT (PRED n))) 1
用 Y-组合子 在 λ语言 中合法地定义：
FACT = Y (λ g.λ n.n (λ u.MULT n (g (PRED n))) 1)
Y = λ f.((λ x.f (x x)) (λ x.f (x x)))
递归是一种以函数自身迭代自身变元的算法,一般是通过函数自身来定义函数的方式实现.表面看来 lambda 演算不允许递归,其实这是一种对递归的误解.考虑阶乘函数 f(n) 一般这样递归地定义：
f(n) = 1,若 n = 0; n•f(n-1),若 n>0.
λ语言：
FACT = λ n.n (λ u.MULT n (FACT (PRED n))) 1
用 Y-组合子 在 λ语言 中合法地定义：
FACT = Y (λ g.λ n.n (λ u.MULT n (g (PRED n))) 1)
Y = λ f.((λ x.f (x x)) (λ x.f (x x)))