(d) f x x
N
( ) =
2 over .
The function is defined for all natural numbers.
(e) f x
x
x
( ) =
+
+
5
2
6
3
2
.
The function is defined for all natural numbers.
6.4 COMPOSITION AND RECURSION
If g 1 , g 2 , g 3 and h are previously defined functions, these functions can be
combined to form new functions. These functions can be combined only in
precisely defined ways.
(a) Composition: f x y h g x y g x y
( , )
( ( , ), ( , ))
=
1
2
. This allows us to use
functions as arguments to functions.
(b) Primitive Recursion: This is a structured “recursive routine” with the
form:
f x
g x
f x s y
h g x y g f x y
( , )
( )
( , ( ))
( ( , ), ( ( , )))
0
1
2
3
=
=
“A primitive recursive function is a function formed from the
functions z, s, p 1 and p 2 by using only composition and primitive
recursion”.
The recursion should be guaranteed to terminate. In order to ensure this,
the function should carry along an extra parameter that is “decremented” every
time the function is called [s(x) replaced by x], and halts the recursion when it
reaches “zero” (z(x)), i.e.,
f
z x
f
s x
f
x
(
, ( ))
(
, ( ))
(
, ),
KK
KK
KK
KK KK
KK
=
=
The recursive function should appear only once in the definitions (RHS of
the definition). This in fact, avoids various forms of “fancy” recursion.
Examples: The following examples show how these can be used to define
more complicated functions.
(a) Addition of two numbers: According to the form, it is:
add
add
add
( , ( ))
( )
( , ( ))
( ( , ), (
( , )
x z x
g x
x s y
h g x y g
x y
=
=
1
2
3
))
By choosing g
p g
p g
s
h p
1
1
2
1
3
2
=
=
=
=
,
,
,
and
we get
add
add
add
( , ( ))
( )
( , ( ))
( ( , ), (
( , )
x z x
p x
x s y
p p x y s
x y
=
=
1
2
1
))
222
Theory of Automata, Formal Languages and Computation
N
( ) =
2 over .
The function is defined for all natural numbers.
(e) f x
x
x
( ) =
+
+
5
2
6
3
2
.
The function is defined for all natural numbers.
6.4 COMPOSITION AND RECURSION
If g 1 , g 2 , g 3 and h are previously defined functions, these functions can be
combined to form new functions. These functions can be combined only in
precisely defined ways.
(a) Composition: f x y h g x y g x y
( , )
( ( , ), ( , ))
=
1
2
. This allows us to use
functions as arguments to functions.
(b) Primitive Recursion: This is a structured “recursive routine” with the
form:
f x
g x
f x s y
h g x y g f x y
( , )
( )
( , ( ))
( ( , ), ( ( , )))
0
1
2
3
=
=
“A primitive recursive function is a function formed from the
functions z, s, p 1 and p 2 by using only composition and primitive
recursion”.
The recursion should be guaranteed to terminate. In order to ensure this,
the function should carry along an extra parameter that is “decremented” every
time the function is called [s(x) replaced by x], and halts the recursion when it
reaches “zero” (z(x)), i.e.,
f
z x
f
s x
f
x
(
, ( ))
(
, ( ))
(
, ),
KK
KK
KK
KK KK
KK
=
=
The recursive function should appear only once in the definitions (RHS of
the definition). This in fact, avoids various forms of “fancy” recursion.
Examples: The following examples show how these can be used to define
more complicated functions.
(a) Addition of two numbers: According to the form, it is:
add
add
add
( , ( ))
( )
( , ( ))
( ( , ), (
( , )
x z x
g x
x s y
h g x y g
x y
=
=
1
2
3
))
By choosing g
p g
p g
s
h p
1
1
2
1
3
2
=
=
=
=
,
,
,
and
we get
add
add
add
( , ( ))
( )
( , ( ))
( ( , ), (
( , )
x z x
p x
x s y
p p x y s
x y
=
=
1
2
1
))
222
Theory of Automata, Formal Languages and Computation