Recursive Functions

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 variable is considered as f 1, x_2,...,x_n>.

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

On the other hand, if f: D ® N where D Í Nⁿ, then f is called partial.



Examples:

1. f = x+y which is defined for all x, y N and hence is a total function.
2. g = x-y which is defined for only those x, y N, which satisfy x > y.
   Hence g 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 f₁ , f₂ and g be any three functions. The composition of g with f₁, and f₂ is a function h
given by h = g 1, f₂>


For h to be non-empty, it is necessary that the domain of g include where and are the ranges of f₁ and f₂
respectively. Also the domain of h is where and are the domains of f₁ and f₂ respectively.

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

h1,x₂,....,x_m> = g11,x₂,…,x_m>,…,f_n1,x₂,…,x_m>>.

It is assumed that the domain of g includes the n - tuples , I_n={1,2,.....,n} and denotes the range of f_i. Also the
domain of h is given by ,where is the domain of f_i. The function h is total iff f₁, f₂,...,f_n, and g are total.

Let f₁ = x+y,

f₂ = xy+y² and

g = xy.

Then, h = g1,f₂>
= g2>
= (x+ y)(xy+y²).

Here h is total, because f₁, f₂, and g are all total.

Given a function f1,x₂,...,x_n> 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 to obtain
f,f,f,……

Example:

If f = 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 f1,x₂,…,x_n,y> of n+1 variables by using two other functions
g1,x₂,…,x_n> and h1,x₂,…,x_n,y,z> of n and n+2 variables, respectively, is called recursion.

f1,x₂,...,x_n,0> = g1,x₂,...,x_n>
f1,x₂,...,x_n,y+1> = h1, x₂,...,x_n ,y,f1,x₂,...,x_n,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 x₁,x₂,…, x_n 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.

Back to top

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 f₁,f₂,…,f_k 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 is primitive recursive.

Solution:
x+(y+1) = (x+y)+1.
Therefore f = f+1 = S(f) and

f = x.

Define f as

f = x = and
f = S (<> > ).

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

f<2,> = S(f<2,>
= S(S(f<2,>))
= S(S(S(f<2,>)))
= S(S(S(S(f<2,>))))
= 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.

Solution:

Since g = 0 and g = g + x, we write
g = Z(x).
g(x, y + 1) = f < <>>, >> 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(<>)).

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) = (r (y)>))
   P_r(0) = 0, P_r(1) = 1, P_r(2) = 0, P_r(3) = 1, ……
   
5. Proper subtraction function, • :
   x • 0 = x, x • (y + 1) = p ( x • y).
   Note that x • y = 0 for 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 = maximum of x and y
   = y + (x • y).
   
8. The square function, f(y) = y²
   f(y) = y² = (y) * (y)

Example 3:

Show that f = x^y is primitive recursive function.

Solution:

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

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

f = sg(x).

f = x * f
= <>> * <>>



Example 4:

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

Solution:

For y=0, f = 0.
Also the value of f 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).

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

Also this other function must be 1 whenever S(f) x.
But S(f) is always x and hence such a function is sg ( x • S(f)).

Thus the required definition of fis
f = 0

f = S(f) * sg (x • S(f)).



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] + P_r(y)
where P_r(y) denotes the parity function which is 1 when y is odd and which is 0 when y is even.

Back to top

4.1.3 Primitive Recursive Set

Any set R Í Nⁿ defines a number - theoretic n-ary relation.

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



Here R Í Nⁿ and 1, x₂, . . ., x_n> Nⁿ.

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 N} which defines the relation of equality is primitive recursive.

Solution:

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

Thus f is the required characteristic function which is primitive recursive.



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

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


Example 3:
Show that the function f1, x₂, y> defined as


Is primitive recursive.

Solution:

The required function can be expressed as

x₂ + (x₁ * y) * (x₁ • y).

Back to top

4.1.4 Recursive Function

Regular Function:

Let g <>1, x₂,…, x_n, y > be a total function. If there exists atleast one value of y, say Î N, such that the function
g <>1, x₂,…, x_n, > = 0 for all n - tuples <>1, x₂,…,x_n > Î Nⁿ then g is called a regular function.

Not all total functions are regular, as can be seen from g <> = | y² – x |. g <> is total, but |y²–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
| y² – 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 1, x₂,…, x_n> is said to be defined from a total function g <>1, x₂, ..., x_n, y> by minimization or
m operation if



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

From the definition it follows that f <>1, x₂, … , x_n > 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 = |2y – x|.

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

Define f(x) = m _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)² • x is zero for (y + 1)² £ x and non-zero for (y + 1)² > x.

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

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

[] = m _y(((y + 1)² • x)) = 0.

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

Back to top

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 AB and AB 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 Y_P denotes the characteristic function of the
predicate P, then Y_P = Y_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.

Y_{P Ú Q} = Y_{AÈ B} Y_{P Ù Q} = Y_{A Ç B} Y_{ù P} = Y_{~ 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 . If a number x divides y, then the remainder is 0 and (rm) = 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 f1,x₂,…,x_n,y> using recursion, x₁,x₂,…,x_n 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 is defined by

A<> = y + 1.
A<> = A <>.
A <> = A <>>.

A is well defined and total. A is not primitive, but recursive.


Example 5:

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

Solution:

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

A<> = 2
A<> = A<>
= 3

A<> = A<>
= A<>>
A<> = A<>>
= A<>
= 4

A<> = A<>
= 5

A<> = A<>
= A<>>

A<> = A<>>
A<> = A<>>
= A<>
= 5

A<> = A<>
= 6

A <> = A <>
= 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 <>
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