The document Recursive Function Theory Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**Recursive Function Theory**

A function that calls itself directly or indirectly is called a recursive function. The recursive factorial function uses more memory than its non-recursive counter part. Recursive function requires stack support to save the recursive function calls.

- Recursion leads to compact
- It is simple
- It is easy to understand
- It is easy to prove correct

**Functions**

The concept of a function is a fundamantal topic in mathematics.

A function or a total function f : X →Y is a rule that assigns to all the elements of one set, X, a unique element of another set, Y.

The first set, X is called the domain of the function, and the second set, Y is called its range.

For example, f(x) = 2x + 1 is a function defined on one variable, x. Imagine we say that f is over all natural numbers only. Then the following diagram shows the function:

Here the domain of f is {1, 2, 3, 4, ......}

Range of f is {3, 5, 7, 9, ........}.

f(x; y) = x^{2 }+ 2y is a function on 2 variables, x and y.

f(x, y, z) = x + 2y^{3} + 7z is a function on 3 variables, x, y and z.

__Total Function__

The above three examples were total functions. A total function from X to Y is a rule that assigns to every element of X, a unique element of Y.

f : X → Y

For example, f(x) = 2x^{3}

In all our discussions, we assume that f is over all natural numbers, then

Here the domain of f is {1, 2, 3, 4 .....}.

That is, the domain contains all the elements of x. So f is a total function.

__Partial Function__

Here, to extend the class of computable functions, we use partial functions.

A partial function, f : X→ Y

is a rule that assigns to some elements of X, a unique element of Y. For other elements, there may not be any corresponding element in Y.**Example 1:**

Suppose f is defined over natural numbers. Then f is a partial function. this can be seen from the following diagram.

In the above diagram, domain of f is {2, 4, 6, 8, ....}

Here the domain is not equal to the set X. So f is a partial function.

**Example 2:**

f(x, y) = x − y

f is defined over N. f is a partial function.

This is because when x=6, y=8, f(x,y) = -2

-2 is not a natural number. So f is not defined for x=6, y=8. f is a partial function.

__Recursive Functions__

Consider the example,

f(n) = n^{2} + 1

Here, given any value for n, multiply that value by itself and then add one. Here function is defined in a recursive way. Value of f can be computed in a mechanical fashion.

**Example 1:**

Factorial of a number is defined as,

n! = n (n-1) (n-2) . . . . . . 1.

This is an explicit definition. Another way to define factorial is,

0! = 1

n! = n (n-1)!

for n∈N, This definition is recursive because to find the factorial at an argument n, we need to find the factorial at some simpler argument (n-1).

**Example 2:**

Exponentiation can be defined as, x

n = x.x.x.x......x (n times)

This exponentiation function can be recursively defined as,

x^{0} = 1

x^{n} = x.x^{n}−1

for n∈N. This is a recursive definition for exponentiation.

In all our discussions, a function, f is defined over natural numbers (N) only.

__Primitive Recursive Functions__

A function, f is called a primitive recursive function,

i) If it is one of the three basic functions, or,

ii) If it can be obtained by applying operations such as composition and recursion to the set of basic functions.

The basic functions and operations are explained below:

**1. Basic Functions**

**Zero Function**

Z(x) = 0 is called Zero function.

Example: We may write, Z(8) = 0**Successor Function**

The successor function is S(x), defined as

S(x) = x+1

Thus the value of S(x) is the integer next in sequence to x.

For example,

S(4) = 5, S(29) = 30**Projector Function**

Projector function, P_{k}is defined as,

P_{k}(x_{1}, x_{2}, ..........x_{k}, ...........x_{n}) = x_{k}

For example,

P_{3}(8, 5, 6, 4) = 6

P_{6}(6, 34, 7, 2, 45, 23, 22) = 23

**2. Operations**

We can build complicated functions from the above basic functions by performing operations such as, composition, and recursion.

**Composition**

If functions, f_{1}, f_{2 }and g are given, then the composition of g with f_{1}, f_{2}is given by,

h = g(f_{1}, f_{2}).

In general, If functions f_{1}, f_{2} .....f_{k }and g are given, then the composition of g with f_{1}, f_{2} .....f_{k} is h = g(f_{1}, f_{2} , f_{3}......f_{k})

**Example 1:**

Let g(n) = n^{2}_{,}^{ }h(n) = n + 3

Find the composition of h with g.

The composition of h with g is,

f(n) = h[g(n)]

= h[n^{2}]

= n^{2} + 3

**Example 2:**

Let g(n) = n^{2}_{, }h(n) = n + 3

Find the composition of g with h.

f(n) = g[h(n)]

= g[n + 3]

= (n + 3)^{2}

**Example 3:**

Let, f_{1}(x, y) = x + y

f_{2}(x, y) = 2x

f_{3}(x, y) = xy, and

g(x, y, z) = x + y + z

be functions over N.

Find the composition of g with f_{1}, f_{2} , f_{3.}

h(x, y) = g(f_{1}, f_{2} , f_{3})

= g (x + y, 2x, xy)

= x + y + 2x + xy

= 3x + y + xy

**Recursion**

A function f can be constructed using recursion from the functions g and h as,

f(x, 0) = g(x)

f(x, y + 1) = h [x, y, f(x, y)]

In the above, f is of two variables. g is of one variable and h is of 3 variables.

In general, a function of n+1 variables is defined by recursion if there exists a function g of n variables and a function h of n+2 variables.

f is defined as,

f(x_{1,} x_{2}, .....x_{n}, 0) = g(x_{1,} x_{2}, ...x_{n})

f(x_{1,} x_{2}, .....x_{n}, y + 1) = h [x_{1,} x_{2}, ..........x_{n}, y, f(x_{1,} x_{2}, ..........x_{n}, y) ]

**Example 1:**

Addition of integers can be defined using recursion as,

add(x, 0) = x

add(x, y + 1) = add(x, y) + 1

**Example 2:**

The function multiplication can be defined using recursion operation as,

prod(x, 0) = 0

prod(x, y + 1) = add [x, prod(x, y) ]

Above examples show how recursion operation is applied to a set of functions.

** Primitive Recursive Functions : **Now we learned basic functions such as zero function, successor function and projector function, and operations such as composition and recursion.

Again, a function, f is a primitive recursive function if either,

i. it is one of the basic functions, or

ii. it is produced by performing operations such as composition and recursion to the basic functions.

**Example 1:**

The addition function, add(x,y) is a primitive recursive function because,

add(x, 0) = x

= P_{1}(x)

add(x, y + 1) = add(x, y) + 1

= S[add(x, y)]

= S[P_{3}(x, y, add(x, y))]

Thus add(x, y) is a function produced by applying composition and recursion to basic functions, P_{k} and S.

**Example 2:**

The multiplication function mult(x, y) is a primitive recursive function because,

mult(x, 0) = 0

= Z(x)

mult(x, y + 1) = add [x, mult(x, y) ]

= add[P1(x, y, mult(x, y)), P3(x, y, mult(x, y))]

From the previous example, add() is a primitve recursive function.

From the above, mult(x,y) is produced by performing operations on basic functions and add() function.

So mult(x,y) is a primitive recursive function.

**Example 3:**

The factorial function,

f(n) = n!

is a primitive recursive function. This can be proved using mathematical induction.

Basic Step:

For n = 0,

f(0) = 0! = 1

= P_{1}(1)

Induction Hypothesis:

Assume that f(p) is a primitive recursive function.

Induction Step:

f(p+1) = (p+1)!

= p! (p+1)

= f(p) (p+1)

= mult [ f(p), p+1 ]

= mult [ f(p), S(p) ]

In the above, f(p) is primitive recursive from induction hypothesis.

S(p) is primitive recursive, since it is the successor function. mult() is primitve recursive from the previous example.

So we can conclude that

f(n) = n!

is primitive recursive.

**Example 4:**

Show that function f_{1}(x, y) = x + y is primitive recursive.

f_{1}(x, 0) = x + 0

= x

= P1(x)

f_{1}(x, y + 1) = x + (y + 1)

= (x + y) + 1

= f_{1}(x, y) + 1

= S[f_{1}(x, y)]

= S[P_{3}(x, y, f_{1}(x, y))]

Since f1(x, 0) and f_{1}(x, y + 1) are primitive recursive, f_{1}(x, y) = x + y is primitive recursive.

**Example 5:**

Show that the function, f_{1}(x, y) = x ∗ y is primitive recursive.

f_{2}(x, 0) = x ∗ 0

= 0

= Z(x)

f_{1}(x, y + 1) = x ∗ (y + 1)

= (x ∗ y) + x

= f2(x, y) + x

= f_{1}[f_{2}(x, y), x] from Example 4.

= f_{1}[P_{3}(x, y, f_{2}(x, y)), P_{1}(x, y, f_{2}(x, y))]

Since f_{2}(x, 0) and f_{2}(x, y + 1) are primitive recursive, f_{2}(x, y) = x ∗ y is primitive recursive.

**Example 6:**

Show that the function, f(x, y) = x^{y }is a primitive recursive function.

f(x, 0) = x^{0}

= 1

= P_{1}(1)

f(x, y + 1) = x^{y}+1

= x^{y}.x^{1}

= x.x^{y}

= x.f(x, y)

= P1(x, y, f(x, y)) ∗ P3(x, y, f(x, y))

= mult [P1(x, y, f(x, y)), P3(x, y, f(x, y)) ]

mult() is a primitive recursive function as we found earlier.

Since f(x, 0) and f(x, y + 1) are primitive recursive, f(x, y) = x^{y }is primitive recursive.

__Partial Recursive Functions__

A function, f is a partial recursive function if either,

i. it is one of the basic functions, or

ii. it is produced by performing operations such as composition, recursion and minimization to the basic functions.

**Basic Functions:**We learned three basic functions such as,

- Zero function, Z(x)

- Successor function, S(x)

- Projector function, P_{k}**Operations**

We learned the operations composition and recursion earlier. A new operation now comes, minimization. Minimization μ is the minimization operator.

Let a function g(x,y) is defined over two variables, x and y.

Then minimization operator, μ is defined over g (x, y) is as follows:

μy[g(x, y)] =smallest y such that g (x, y) = 0.

Using the minimization operation, a function f(x) can be defined for some y;

we can write, f(x) = μ_{y}[g(x, y)]

**Example 1:**

Let g(x,y) is given in the following table:

g(0,0)=5 g(1,0)=5 g(2,0)=8 g(3,0)=1

g(0,1)=4 g(1,1)=6 g(2,1)=5 g(3,1)=2

g(0,2)=6 g(1,2)=0 g(2,2)=undefined g(3,2)=0

g(0,3)=0 g(1,3)=3 g(2,3)=0 g(3,3)=4

g(0,4)=1 g(1,4)=0 g(2,4)=7 g(3,4)=undefined

Then,

f(0) = 3,

[ because g(0,3) = 0]

Minimization operation is denoted by μ[g(0, 3) = 0] = 3

f(1) = 2

[ 2 is the minimum y that g(1,2)=0; Though g(1,4)=0 also; ]

Minimization operation is denoted by μ[g(1, 2) = 0] = 2

f(2) = Not defined

[because g(2,3)=0, but g(2,2) is undefined, where y=2 < y=3 ]

f(3) = 2

[because g(3,2)=0, though g(3,4) is undefined for y=4, but 4<2 ]

Minimization operation is denoted by μ[g(3, 2) = 0] = 2

For some values g(x,y) is undefined, but we can define minimization operation.

**Partial Recursive Functions**

A function, f is a partial recursive function if either,

i. it is one of the basic functions, or

ii. it is produced by performing operations such as composition, recursion and minimization to the basic functions.

From the definition, we can say that, primitive recursive functions are a subset of partial recursive functions. This is shown below:

Thus all primitive recursive functions are partial recursive functions.

Note that all partial recursive functions are computable functions.

**Example 1:**

Show that

is a partial recursive function over N.

We may write

Then,

x = 2y

2y − x = 0

Let

g(x, y) = |2y − x|

Let

g(x, y) = 0, for some x and y.

Let

f_{1}(x) = μ[|2y − x| = 0]

Only for even values of x , f_{1}(x) is defined. When x is odd, f_{1}(x) is not defined. So f_{1} is partial recursive.

Since, = f_{1}(x), f is a partial recursive function.

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

36 videos|39 docs|39 tests