递归类型

维基百科,自由的百科全书
跳转至: 导航搜索

在计算机编程语言中,递归类型(又名:递归定義隱含類型隱含定義)是一种特殊的数据类型,它表示自身内部可能包含其它的同样类型的值。

範例[编辑]

以下是一個在Haskell中使用链表类型的一个列子:

data List a = Nil | Cons a (List a)

这表示a的链表s可以是一个空表或一个cons单元包含了一个'a'(链表的“头”)和另一个链表(“尾”)。

递归不允许在Miranda语言中和Haskell的同义类型中出现,所以以下的Haskell类型是非法的

type Bad = (Int, Bad)
type Evil = Bool -> Evil

素数计算是递归的[编辑]

若自然数n不能被不大于\sqrt{n}任何素数整除,则n是一个素数。  
  (这句话本身就是一个公式。这个公式可以一个不漏地产生所有素数,而不会混入一个合数)。  
   
  可以把上面的汉字内容等价转换成为英语字母表示:  
   
  n=p_{1}m_{1}+a_{1}=p_{2}m_{2}+a_{2}=\dots=p_{k}m_{k}+a_{k}.(1)  
   
  其中 p_{1},p_{2},\dots,p_{k}表示顺序素数2,3,5,....。a≠0。

即n≠2m_{1}+03m_{2}+05m_{3}+0,...,p_{k}m_{k}+0形。

n<P^{2}_{k+1},则n是一个素数。  
   
  我们可以把(1)式内容等价转换同余式组表示  :
  n \equiv a_1 \pmod{p_1}, n \equiv a_2 \pmod{p_2}, \dots, n \equiv a_k \pmod{p_k}(2)  
   
  由于(2)的模p_{1},p_{2},...,p_{k} 两两互素, 
  根据孙子定理(中国剩余定理)知,对于给定的a_{1},a_{2},...,a_{k},(2)式在p_{1}p_{2}...p_{k}范围内有唯一解。  
   

  范例  
   
  k=1时,n=2m_{1}+1,解得n=3,5,7。求得了(3,3²)区间的全部素数。  
   
  k=2时,n=2m_{1}+1=3m_{2}+1,解得n=7,13,19; n=2m_{1}+1=3m_{2}+2

解得n=5,11,17,23。

  求得了(5,5²)区间的全部素数。  
k=3时 5m_{3}+1 5m_{3}+2 5m_{3}+3 5m_{3}+4
n=2m_{1}+1=3m_{2}+1= 31 7,37 13,43 19
n=2m_{1}+1=3m_{2}+2= 11,41 17,47 23 29
  |}求得了(7,7²)区间的全部素数。  
   
  仿此下去可以求得任意大的数以内的全部素数。并且一个不漏地求得。 
  对于所有可能的a_{1}, a_{2} \cdot , a_{k}值,(1)和(2)式在p_{1}p_{2}...p_{k}范围内,

有(p_{1}-1)(p_{2}-1)(p_{3}-1)...(p_{k}-1) 个解。

(1)式(2)式与哥德巴赫猜想的合理框架 怎样使得两个自然数相加和相减都成为素数,即N+X成为素数,N-X也是素数。 根据除法算式定理:“给定正整数a和b,b≠0,存在唯一整数q和r(0≤r<b),使a=bq+r”。 再根据同余定理:“每一整数恰与0,1,2,3,...,m-1中一数同余(mod m)”。 所以,任给一个自然数N(N>4),都可以唯一表示成为:

N=p_{1}m_{1}+e_{1}=p_{2}m_{2}+e_{2}=\dots=p_{k}m_{k}+e_{k}.(3)

其中 p_{1},p_{2},\dots,p_{k}表示顺序素数2,3,5,....。

e_{i}=0,1,2,...,P_{i}-1

\frac{p^{2}_{k}}{2} < N < \frac{p^{2}_{k+1}}{2}

现在问,是否存在X,

X=p_{1}h_{1}+f_{1}=p_{2}h_{2}+f_{2}=\dots=p_{k}h_{k}+f_{k}.(4)

f_{i}e_{i}

f_{i}p_{i}-e_{i}

如果X<N-2,则N+X与N-X都是素数,因为它们符合(1)(2)式。

範例[编辑]

設N=20,20=2m_{1}+0=3m_{2}+2=5m_{5}+0\frac{5^{2}}{2} < 20 < \frac{7^{2}}{2}

e_{1}=0,e_{2}=2,e_{3}=0.
构造x 5h_{3}+1 5h_{3}+2 5h_{3}+3 5h_{3}+4
X=2h_{1}+1=3h_{2}+0= 21 27 3 9

f_{i}e_{i}f_{i}p_{i}-e_{i}

f_{1}=1f_{2}=0f_{3}=1. f_{1}=1f_{2}=0f_{3}=2. f_{1}=1f_{2}=0f_{3}=3. f_{1}=1f_{2}=0f_{3}=4.

四个解是:21,27,3,9。小于N-2的X有3和9,我们得知,20+3与20-3是一对素数;20+9与20-9是一对素数。 这就是利用素数判定法则:最小剩余不为零,并且N+X<P^{2}_{k+1},则N+X与N-X是一对素数。 因为(N+X)+(N-X)=2N。这就是著名的哥德巴赫猜想猜想我们需要证明(4)式必然有小于N-2的解,尽管我们现在不能证明它


孪生质数的公式也是递归的[编辑]

利用上述定理,可以得到以下的结论:“若自然数z+1z-1都不能被任何不大于\sqrt{z+1}的质数 整除,则z + 1z - 1都是质数”。 用数学的语言表示以上的结论,就是:

存在一组自然数b_{1}, b_{2} \cdot , b_{k},使得
z=p_{1}m_{1}+b_{1}=p_{2}m_{2}+b_{2}=\dots=p_{k}m_{k}+b_{k} \qquad \qquad \qquad \cdots \qquad (5)

其中 p_{1},p_{2},\dots,p_{k}表示从小到大排列时的前k个质数:2,3,5,....。并且满足

\forall 1 \le i  \le k, \ \  b_{i} < p_{i}, \ b_{i} \neq 1, \ b_{i} \neq p_{i} - 1.

这样解得的自然数z如果满足z<p^{2}_{K+1}-1,则z + 1z - 1是一对孪生质数。 我们可以把(5)式的内容等价转换成为同余方程组表示:

z \equiv b_1 \pmod{p_1}, z \equiv b_2 \pmod{p_2}, \dots, z \equiv b_k \pmod{p_k} \qquad \qquad \qquad  \cdots \qquad (6)

由于(6)的模p_{1},p_{2},...,p_{k}都是质数,因此两两互质,根据孙子定理(中国剩余定理)知,对于给定的b_{1}, b_{2} \cdot , b_{k},(4)式有唯一一个小于p_{1} p_{2} \cdots p_{k}的正整数解。 例如k=1时,z=2m_{1}+0,解得z=4, 6。由于6<3^2-1,所以可知4+14-16+16-1都是孪生质数。这样就求得了区间(3, 3^2)里的全部孪生质数对。

又比如k=2时,列出方程z=2m_{1}+0=3m_{2}+0,解得z=6, 12, 18。由于18<5^2-1,所以12+112-118+118-1都是了孪生质数。由于这已经是所有可能的b_{1}, b_{2} \cdot , b_{k}值,所以这样就求得了区间(5, 5^2)的全部孪生质数对。

k=3时 5m_{3}+0 5m_{3}+2 5m_{3}+3
z=2m_{1}+0=3m_{2}+0= 30 12,42 18

30±1和42±1都是孪生素数.

由于这已经是所有可能的c_{1}, c_{2} \cdot , c_{k}值,所以这样就求得了区间(7, 7^2)的全部孪生质数对。

k=4时 7m_{4}+0 7m_{4}+2 7m_{4}+3 7m_{4}+4 7m_{4}+5
z=2m_{1}+0=3m_{2}+0=5m_{3}+0= 210 30 150 60 180
z=2m_{1}+0=3m_{2}+0=5m_{3}+2= 42 72 192 102 12
z=2m_{1}+0=3m_{2}+0=5m_{3}+3= 168 198 108 18 138

小于121-1的8个解z±1就是是孪生素数. 由于这已经是所有可能的c_{1}, c_{2} \cdot , c_{k}值,所以这样就求得了区间(11, 11^2)的全部孪生质数对。

仿此下去可以一个不漏地求得任意大的数以内的全部孪生质数对。对于所有可能的b_{1}, b_{2} \cdot , b_{k}值,(3)和(4)式在p_{1}p_{2}...p_{k}范围内,有 :(p_{1}-1)(p_{2}-2)(p_{3}-2)...(p_{k}-2)。(**)个解。

孪生质数猜想就是在k值任意大时(3)和(4)式都有小于p^{2}_{k+1}-1的解。实际上,孪生素数猜想已经转入初等数论的范围。(

data Good = Pair Int Good
data Fine = Fun (Bool->Fine)

本條目部分或全部内容出自以GFDL授權發佈的《自由線上電腦詞典》(FOLDOC)。