Recursive Functions

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 , 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,…,fn<x1,x2,…,xm>>. It is assumed that the domain of g includes the n - tuples and denotes the range of fi. Also the domain of h is given by domain of fi. The function h is total iff f1, f2,...,fn, and g are total.

, In={1,2,.....,n} ,where

is the

Let f1<x, y> = x+y, f2<x,y> = xy+y2 and g<x,y> = xy. Then, h<x,y> = g,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>>, function given in Example 1.

<x, y, g<x, y>>> where f is the addition

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,

:

< y, sg(y)>)).

(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) =

(

))

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.

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 recursive.

x/2 primitive

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 { / 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) *

4.1.4

(x1 • y).

Recursive Function

Regular Function: Let g < x1, x2,…, xn, y > be a total function. If there exists atleast one value of y, say such that the function g < x1, x2,…, xn, called a regular function.

∈ N,

> = 0 for all n - tuples < x1, x2,…,xn > ∈Nn then g is

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 [ [

] = μ y(

Note that [

4.1.5

] , hence

((y + 1)2 • x)) = 0. ] is defined for all x and hence is a recursive function.

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

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:

, the

A number x 1 ≤i ≤n.

n is a divisor of n iff | x * i - n| is equal to zero for one fixed value of i,

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 by

(rm<x, y>) = 1. Therefore the number of divisors of y is given

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. 2. 3. 4.

Set j ←2. If j ≥ i then output " i is prime" and Exit. If j / i then output " i is not prime" and Exit. 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. Set k ← i. Set k ←k + 1. Set SUM ←0. Set j ←1. If j < k then go to step 7. 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.   1. 2. 3. 4. 5. 6.