4.

1 Recursive Functions

4.1.1 Basics

Consider only those functions whose arguments and values are natural numbers. Such
functions are called number - theoretic. In general number - theoretic function in n variables
is considered as f <x1, x2,...,xn>.

Any function f : Nn → N is called total because it is defined for every n-tuple in Nn.

On the other hand, if f: D → N where D ⊆ Nn, then f is called partial.

Examples:

1. f<x, y> = x+y which is defined for all x, y N and hence is a total function.
2. g<x, y> = x-y which is defined for only those x, y N, which satisfy x > y.
Hence g <x, y> is partial.

Every total function of n variables is also a n - ary operation on N.

Initial Functions:

Consider a set of three functions called the initial functions, which are used in defining other
functions by induction.

Z : Z(x) = 0 Zero function

S : S(x) = x+1 Successor function

The projection function is also called generalized identity function.

Examples:

The operation of composition will be used to generate other functions. Composition of

functions idea can be extended to functions of more than one variable.

For example, let f1<x, y> , f2<x, y> and g<x, y> be any three functions. The composition of g
with f1, and f2 is a function h given by h<x, y> = g <f1<x, y>, f2<x, y>>

For h to be non-empty, it is necessary that the domain of g include where

and are the ranges of f1 and f2 respectively. Also the domain of h is

where and are the domains of f1 and f2 respectively.

If f1, f2 and g are total, then h is also total. In general, let f1, f2, …, fn each be partial functions
of m variables, and let g be a partial function of n variables. Then the composition of g with
f1,f2,…,fn produces a partial function h given by

h<x1,x2,....,xm> = g<f1<x1,x2,…,xm>,…,fn<x1,x2,…,xm>>.

It is assumed that the domain of g includes the n - tuples , In={1,2,.....,n}

and denotes the range of fi. Also the domain of h is given by ,where is the
domain of fi. The function h is total iff f1, f2,...,fn, and g are total.

Let f1<x, y> = x+y,

f2<x,y> = xy+y2 and

g<x,y> = xy.

Then, h<x,y> = g<f1<x,y>,f2<x,y>>

= g<x+y,xy+y2>
= (x+ y)(xy+y2).

Here h is total, because f1, f2, and g are all total.

Given a function f<x1,x2,...,xn> of n variables and consider n - 1 of the variables as fixed and
vary only the remaining variable over the set of natural numbers or over a subset of it. For
example, fix x and vary y in f<x,y> to obtain f<x,0>,f<x,1>,f<x,2>,……

Example:

If f<x,y> = x+y and f<2,0> = 2, find f<2,3>.

Solution:

First evaluate f<2,1>, f<2,2> and finally f<2,3>. Each functional value is computed by
adding 1 to the previous value until the desired result is obtained.

The computation of f<2,3> is

f<2,3> = [(f<2,0>+1)+1]+1
= [(2+1)+1)+1
= [3+1]+1
= 4+1
= 5.
Recursion:

It is assumed that we have a mechanism by which we can determine the value of the function
when an argument is zero and also its value for the argument n + 1 from the value of the
function when the argument is n. The arguments which are considered to be fixed are
called parameters, while the one which is assumed to vary is considered a variable.

The following operation which defines a function f<x1,x2,…,xn,y> of n+1 variables by using
two other functions g<x1,x2,…,xn> and h<x1,x2,…,xn,y,z> of n and n+2 variables,
respectively, is called recursion.

f<x1,x2,...,xn,0> = g<x1,x2,...,xn>
f<x1,x2,...,xn,y+1> = h<x1, x2,...,xn ,y,f<x1,x2,...,xn,y>>

In this definition, the variable y is assumed to be the inductive variable in the sense that the
value of f at y +1 is expressed in terms of the value of f at y. The variables x1,x2,…, xn are
treated as parameters and are assumed to remain fixed throughout the definition. Also it is
assumed that both the functions g and h are known. We shall now impose restrictions on g
and h which will guarantee that the function f which is defined recursively, as above, can
actually be computed and is total.

4.1.2 Primitive Recursive Function

A function f is called primitive recursive iff it can be obtained from the initial functions by a
finite number of operations of composition and recursion

From the definition it follows that it is not always necessary to use only the initial functions
in the construction of a particular primitive recursive function. If we have a set of functions
f1,f2,…,fk which are primitive recursive, then we can use any of these functions along with
the initial functions to obtain another primitive recursive function, provided we restrict
ourselves to the operations of composition and recursion only.

In the examples given here, first we construct some primitive recursive functions by using the
initial functions alone, and then we use these functions wherever required in order to
construct other primitive recursive functions. All primitive recursive functions are total.

Example 1:

Show that the function f<x,y> = x+y is primitive recursive.

Solution:
x+(y+1) = (x+y)+1.
Therefore f<x,y+1> = f<x,y>+1 = S(f<x,y>) and f<x,0> = x.

Define f<x,y> as

f<x, 0> = x = and

f<x, y+1> = S ( < x , y , f< x , y > > ).

Here the basic function is

g(x) = .
and the inductive step function is
h<x, y, z> = S ( <x, y, z>).
For example using these definition, we can compute the value of f<2, 4> we have
f<2, 0> = 2.

f<2, 4> = S(f<2, 3>

= S(S(f<2, 2>))
= S(S(S(f<2, 1>)))
= S(S(S(S(f<2, 0>))))
= S(S(S(S(2))))
= S(S(S((3))))
= S(S(4)) = S (5) = 6

Example 2:

Using recursion, define the multiplication function * given by g<x, y> = x y.

Solution:

Since g<x, 0> = 0 and g<x, y + 1> = g<x, y> + x, we write g<x, 0> = Z(x).
g(x, y + 1) = f < < x, y, g<x, y>>, <x, y, g<x, y>>> where f is the addition
function given in Example 1.

The following are some of the primitive recursive functions which are used frequently.

1. Sign function or non zero test function, sg :

sg(0) = 0 sg (y+1) = 1 or

sg(0) = Z(0) sg(y+1) = S(Z( < y, sg(y)>)).

2. Zero test function, : (0) = 1, (y + 1) = 0.

3. Predecessor function, P :

P(0) = 0 P(y+1) = y = (y, P(y)).

Note that: P(0) = 0 , P(1) = 0 , P(2) = 1 , P(3) = 2.
 4. Odd and even parity function, Pr :

Pr(0) = 0, Pr(y + 1) = ( <y, Pr (y)>))

Pr(0) = 0, Pr(1) = 1, Pr(2) = 0, Pr(3) = 1, ……

5. Proper subtraction function, • :

x • 0 = x, x • (y + 1) = p ( x • y).

Note that x • y = 0 for x<y and x • y = x - y for x y.

6. Absolute value function, | | :

|x – y| = (x • y) + (y • x)

7. min (x , y) = minimum of x and y

min (x , y) = x • (x • y).
max <x, y> = maximum of x and y
= y + (x • y).

8. The square function, f(y) = y2

f(y) = y2 = (y) * (y)

Example 3:

Show that f<x, y> = xy is primitive recursive function.

Solution:

Note that x0 = 1 for x 0 and we put x0 = 0 for x = 0.

Also xy+1 = xy * x ; hence f< x , y > = xy is defined as

f<x, 0> = sg(x).

f<x, y+1> = x * f<x, y>

= < x , y , f<x, y>> * < x , y , f<x, y>>

Example 4:

Show that if f<x, y> defines the remainder upon division of y by x, then it is a primitive
recursive function.

Solution:

For y=0, f<x , 0> = 0.

Also the value of f<x, y> increases by 1 when y is increased by 1, until the value becomes
equal to x, in which case it is put equal to 0 and the process continues.

We therefore build a function which increases by 1 each time y increases by 1, that is, S(f<x,
y>).

Now we multiply this function by another primitive recursive function which becomes 0
whenever S(f<x, y>) = x .

Also this other function must be 1 whenever S(f<x, y>) x.

But S(f<x, y>) is always x and hence such a function is sg ( x • S(f<x, y>)).

Thus the required definition of f<x, y>is f<x, 0> = 0

f<x, y + 1> = S(f<x, y>) * sg (x • S(f<x, y>)).

Example 5:

Show that the function [x/ 2] which is equal to the greatest integer which is x/2 primitive
recursive.

Solution:

Now [0/2] = 0.
[1/2] = 0.
[2/2] = 1.
[3/2] = 1, etc., so that [x/2] = x/2 when x is even and [x/2] = (x-1)/2 when x is odd.

In order to distinguish between even and odd functions, we have defined the parity function,
which is primitive recursive.
[0/2] = 0,

[(y+1)/2] = [y/2] + Pr(y)

where Pr(y) denotes the parity function which is 1 when y is odd and which is 0 when y is
even.

4.1.3 Primitive Recursive Set

Any set R ⊆ Nn defines a number - theoretic n-ary relation.

The characteristic function of a relation R can be now defined as

Here R ⊆ Nn and <x1, x2, . . ., xn> Nn.

A relation R is said to be primitive recursive if its characteristic function is primitive

recursive. The corresponding predicate is also called primitive recursive.

Example 1:
Show that {<x, x> / x N} which defines the relation of equality is primitive recursive.

Solution:

Obviously f<x, y> = (| x – y |) defines a primitive recursive function such that f<x, y> = 1
for x = y and otherwise f<x , y> = 0.

Thus f<x, y> is the required characteristic function which is primitive recursive.

Example 2:
Show that for any fixed k the relation given by {<k, y> / y > k} is primitive recursive.

Solution:
sg(y • k) is the characteristic function of the required relation.

Example 3:
Show that the function f<x1, x2, y> defined as

Is primitive recursive.

Solution:

The required function can be expressed as

x2 + (x1 * y) * (x1 • y).

4.1.4 Recursive Function

Regular Function:

Let g < x1, x2,…, xn, y > be a total function. If there exists atleast one value of y, say ∈ N,
such that the function g < x1, x2,…, xn, > = 0 for all n - tuples < x1, x2,…,xn > ∈Nn then g is
called a regular function.

Not all total functions are regular, as can be seen from g < x, y > = | y2 – x |. g < x , y > is
total, but |y2–x| = 0 for only those values of x which are perfect squares and not for all values
of x. This fact shows that there is no value of y ∈N such that | y2 – x | = 0 for all x. On the
other hand, the function y • x is regular because for y=0, y • x is zero for all x.

Minimization:

A function f <x1, x2,…, xn> is said to be defined from a total function g < x1, x2, ..., xn, y>
by minimization or μ -operation if

where μ y means the least y greater than or equal to zero.

From the definition it follows that f < x1, x2, … , xn > is well-defined and total if g is regular.
If g is not regular, then the operation of minimization may produce a partial function.

Recursive Function:

A function is said to be recursive iff it can be obtained from the initial functions by a finite
number of applications of the operations of composition, recursion, and minimization over
regular functions.

It is clear from the definition that the set of recursive function properly includes the set of
primitive recursive functions. Also the set of recursive functions is closed under the
operations of composition, recursion, and minimization over regular functions.

Partial Recursive Function:

A function is said to be partial recursive iff it can be obtained from the initial functions by a
finite number of applications of the operations of composition, recursion, and minimization.

Example 1:

Show that the function f (x) = x/2 is a partial recursive function

Solution:
Let g <x, y> = |2y – x|.

The function g is not regular because |2y – x| = 0 only for even values of x.

Define f(x) = μ y ( | 2y – x| ), then f (x) = x/2 for x even.

Example 2:

Let [ ] be the greatest integer . Show that [ ] is primitive recursive.

Solution:

Observe that (y + 1)2 • x is zero for (y + 1)2 ≤ x and non-zero for (y + 1)2 > x.

Therefore, ((y + 1)2 • x) is 1 if (y + 1)2 x and cannot be equal to zero.

The smallest value of y for which (y + 1)2 > x is the required number [ ] , hence

[ ] = μ y( ((y + 1)2 • x)) = 0.

Note that [ ] is defined for all x and hence is a recursive function.

4.1.5 Recursive Sets

A set A is called recursive (partial recursive) if its characteristic function is recursive

(partial recursive). For any two sets A and B with characteristic function and , the
characteristic functions of A B and A B can also be obtained.

Example 1: Show that the sets of even and odd natural numbers are both recursive.

Solution:
The parity function is the required characteristic function for the set E of even natural
numbers. Hence E is primitive recursive. Also the set of odd natural numbers is ~E
(complement of E), hence ~E is also primitive recursive.

Example 2: Show that set of divisors of a positive integer n is recursive.

Solution:
A number x n is a divisor of n iff | x * i - n| is equal to zero for one fixed value of i,
1 ≤i ≤n.

This means that | x * i - n | is non zero for all 1 ≤ i ≤ n, if x is not a divisor.

Therefore, the characteristic function of the required set is

where B denotes the set of divisors of n.

Note: A predicate whose extension is a set of integers is said to be a number-theoretic

predicate. Such a predicate is primitive recursive (recursive) iff its extension is primitive
recursive (recursive). The characteristic function of a predicate is the characteristic function
of its extension. If A is the extension of predicate P and ΨP denotes the characteristic function
of the predicate P, then ΨP = ΨA

For example, the predicates "is even" and "is a divisor of n" are recursive because their
extensions are recursive sets. If A and B are the extensions of predicates P and Q
respectively, then by definition, ΨP ∨ Q = ΨA∪B ΨP ∧ Q = ΨA ∩B Ψ⎤P = Ψ~ A
It directly follows that if P and Q are recursive, then so are predicates P ∨Q, P ∧Q, and ⎤ P.

Example 3: Let D (x) denote " number of divisors of x". Show that D(x) is primitive
recursive.

Solution:
We have shown that the function which defines the remainder upon division of y by x is
primitive recursive. We shall denote such a function by rm <x,y> . If a number x divides y,
then the remainder is 0 and (rm<x, y>) = 1. Therefore the number of divisors of y is given
by

This shows that D (y) is primitive recursive.

Example 4: Show that the predicate "x is prime" is primitive recursive.

Solution:
A number x is a prime iff it has only two divisors 1 and x, also if it is not 1 or 0. Therefore,
the characteristic function of the extension of "x is not a prime" is
Note: In our discussion we considered only one induction variable in the definition of
recursion. It is possible to consider two or more induction variables. Note that in the
definition of f<x1,x2,…,xn,y> using recursion, x1,x2,…,xn were treated as parameters
and only y was treated as the induction variable. Now we define a function in which we have
two induction variables and no parameters.

Consider Ackermann's function. The function A<x, y> is defined by

A< 0, y> = y + 1.
A< x + 1, 0> = A < x, 1>.
A < x + 1, y + 1> = A < x, A < x + 1, y >>.

A <x, y> is well defined and total. A <x, y> is not primitive, but recursive.

Example 5:

Evaluate A <2,2> using the above definitions.

Solution:

A< 2, 2 > = A< 1, A< 2, 1 >>

A< 2, 1 > = A< 1, A< 2, 0 >>
A<2, 0> = A< 1,1 >
A< 1, 1 > = A< 0, A<1, 0 > >
= A< 0, A< 0, 1>>

A< 0, 1> = 2
A< 1, 1> = A< 0, 2>
=3

A< 2, 1> = A< 1, 3>

= A< 0, A<1, 2>>
A< 1, 2> = A< 0, A<1,1>>
= A< 0, 3>
=4

A< 2, 1 > = A< 0, 4 >

=5

A< 2, 2 > = A< 1, 5 >

= A< 0, A< 1, 4 >>

A< 1, 4 > = A< 0 , A < 1, 3 >>

A< 1, 3 > = A< 0 , A < 1 , 2 >>
= A< 0, 4 >
 =5

A< 1, 4 > = A< 0, 5 >

=6

A < 2 , 2 > = A < 0, 6 >

= 7.

Algorithm Prime: Given an integer i greater than 1, this algorithm will determine whether
the integer is a prime number. Note that the only divisors of a prime number are 1 and the
number itself.

1. Set j ←2.
2. If j ≥ i then output " i is prime" and Exit.
3. If j / i then output " i is not prime" and Exit.
4. Set j ←j + 1, goto step 2.

Algorithm Perfect: This algorithm decides whether there exists a perfect number greater
than some integer i. Consider the set of all divisors of a number except the number itself. A
perfect number is one whose sum of all such divisors equals the number. The number 6 is
a perfect number since 1 + 2 + 3 = 6.

1. Set k ← i.
2. Set k ←k + 1.
3. Set SUM ←0.
4. Set j ←1.
5. If j < k then go to step 7.
6. If SUM = k then output k and Exit, otherwise go to step 2.
7. If j / k then set SUM ←SUM + j. Set j ←j + 1 and go to step 5.