1 Crore+ students have signed up on EduRev. Have you? 
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 nonrecursive counter part. Recursive function requires stack support to save the recursive function calls.
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 (n1) (n2) . . . . . . 1.
This is an explicit definition. Another way to define factorial is,
0! = 1
n! = n (n1)!
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 (n1).
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
2. Operations
We can build complicated functions from the above basic functions by performing operations such as, composition, and recursion.
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
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.
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.
18 videos44 docs39 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
18 videos44 docs39 tests
