以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  啥叫原始递归？  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=56052)

--  作者：wu5zg
--  发布时间：11/27/2007 8:21:00 AM

--  啥叫原始递归？
啥叫原始递归？
--  作者：Logician
--  发布时间：11/27/2007 1:23:00 PM

--  
搜 "Primitive Recursive Function"
大致地说：如果F(x,0)的值可以直接算出，而且在已知F(x,n)的值情况下，可以直接算出F(x,n+1)的值，那么就说F是原始递归函数。
也即，F(x,0) = H(x)
F(x,n+1) = G(x,n,F(x,n))
其中G和H都是易于计算的函数。

像Fibonacci函数的标准递推式（F(n+2)=F(n+1)+F(n)），在形式上就不是原始递归的，因为已知了F(n)还不能直接算出F(n+1)，需要同时知道F(n)和F(n+1)才能算出F(n+2)。当然，可以通过换一种表达法，把它的定义写成原始递归的形式。

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 31.250ms