请输入您要查询的字词:

 

单词 MutualRecursion
释义

mutual recursion


Mutual recursion is a way of defining functions via recursion involving several functions simultaneously. In mutual recursion, the value of the next argument of any function involved depends on values of the current arguments of all functions involved. The following are two simple examples:

  • the pair of functions f,g such that f(0)=0 and g(0)=1, with f(n+1)=f(n)g(n) and g(n+1)=f(n)+g(n) is defined via mutual recursion. It is easy to see that f(n)=0 and g(n)=1.

  • Fibonacci numbersMathworldPlanetmath can be interpreted via mutual recursion: F(0)=1 and G(0)=1, with F(n+1)=F(n)+G(n) and G(n+1)=F(n).

Formally,

Definition. Functions f1,,fm:k+1 are said to be defined by mutual recursion via functions g1,gm:k and functions h1,,hm:k+m+1, if

fi(𝒙,0)=gi(𝒙),
fi(𝒙,n+1)=hi(𝒙,n,f1(𝒙,n),,fm(𝒙,n)),

for any 𝒙k, and i=1,,m.

Mutual recursion is an apparent generalizationPlanetmathPlanetmath of primitive recursion, where the value of the next argument of a function depends on the value of the current argument of the same function, apparent because it is in fact equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath to primitive recursion.

Proposition 1.

As above, if all of gi and hi are primitive recursive, so are all of fi.

Proof.

We use the multiplicative encoding technique. Define function F:k+1 as follows:

F(𝒙,n)=exp(p1,f1(𝒙,n))exp(pm,fm(𝒙,n)),

where pi is the i-th prime numberMathworldPlanetmath (p1=2, etc…). Furthermore,

(F(𝒙,n))i=fi(𝒙,n),

where (z)i denotes the exponent of prime pi in z. Then

F(𝒙,0)=i=1mexp(pi,gi(𝒙))=G(𝒙), and
F(𝒙,n+1)=i=1mexp(p1,f1(𝒙,n+1))
=i=1mexp(pi,hi(𝒙,n,f1(𝒙,n),,fm(𝒙,n)))
=i=1mexp(pi,hi(𝒙,n,(F(𝒙,n))1,,(F(𝒙,n))m)
=H(𝒙,n,F(𝒙,n))

where

G(𝒙)=i=1mexp(pi,gi(𝒙)),

and

H(𝒙,y,z)=i=1mexp(pi,hi(𝒙,y,(z)1,,(z)m)

Since each of the gi is primitive recursive, G is primitive recursive. Since each of the hi is primitive recursive, H is primitive recursive. So F is primitive recursive, as it is defined via primitive recursion by G and H. Therefore, each fi=(F)i is primitive recursive.∎

Remark. The primitive recursiveness of mutual recursion can be derived from course-of-values recursion. The idea is the following: list the fi’s in order, and construct a single function F so the its values correspond to the values of the fi’s in the order given. For example, if two unary functions f1 and f2 defined by mutual recursion, then

f1(0)f2(0)f1(1)f2(1)f1(2)f1(k)f2(k)f1(k+1)f2(k+1)
F(0)F(1)F(2)F(3)F(4)F(2k)F(2k+1)F(2k+2)F(2k+3)

ThenitisnothardtoseethatF(k+1)dependsonF(k),F(k-1),andF(k-2),andanexplicitformulacanbederivedexpressingthedependency.Furthermore,thisformulaiseasilyseentobeprimitiverecursive,andhencesoisF(k).Titlemutual recursionCanonical nameMutualRecursionDate of creation2013-03-22 19:06:31Last modified on2013-03-22 19:06:31OwnerCWoo (3771)Last modified byCWoo (3771)Numerical id9AuthorCWoo (3771)Entry typeDefinitionClassificationmsc 03D20Synonymsimultaneous recursion

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 6:26:26