Tuesday, November 9, 2010

Ackermann Function A(n,x,y) Examples

11:16 PM 0 comments

Ackermann  Function is an extreme example of Recurrence Relations and
Recursive Functions.
The Ackermann function was discovered and studied by Wilhelm Ackermann (1896–1962) in 1928. Ackermann worked as a high-school teacher from 1927 to 1961 but was also a student of the great mathematician David Hilbert in Göttingen and, from 1953, served as an honorary professor in the university there. Together with Hilbert he published the first modern textbook on mathematical logic.


The Ackermann function can be defined as follows:
     A(0, n) = n + 1 for n = 0 
     A(m, 0) = A(m - 1, 1) for m = 1 
     A(m, n) = A(m - 1, A(m, n - 1)) for m, n = 1


Two positive integers, m and n, are the input and A(m, n) is the output in the form of another positive integer. The function can be programmed easily in just a few lines of code. The problem isn't the complexity of the function but the awesome rate at which it grows. For example, the innocuous-looking A(4,2) already has 19,729 digits!


Definition of Ackermann's Function A(n,x,y):

  • A(0,x,y) = x + 1
  • A(n,x,0) = x     if     n = 1
  • A(n,x,0) = 0     if     n = 2
  • A(n,x,0) = 1     if     n = 3
  • A(n,x,0) = 2     if     n >=4
  • A(n,x,y) = A(n-1,A(n,x,y-1),x)     if     n > 1 and y > 0


Recursive C++ function that calculates values for Ackermann's Function:
int Ackermann(int N, int X, int Y)
{
int K, L;
if (N == 0) return X + 1;
else if ((N > 0) && (Y == 0))
{
if (N == 1) return X;
else if (N == 2) return 0;
else if (N == 3) return 1;
else if (N >= 4) return 2;
else { cout << "Error 1: " << N << ", " << X
<< ", " << Y;
exit(1);
}
}
else if ((N > 0) && (Y > 0))
{ K = Ackermann(N, X, Y - 1);
return Ackermann(N - 1, K, X);
}
else {
cout << "Error 2: " << N << ", " << X << ", " << Y;
exit(1);
}
}

Read More

Recursion function and Fibonacci series

10:49 PM 0 comments

Recursive Function: A recursive function is a function that calls itself, either directly, or indirectly. Recursion is an important topic in upper-level computer science courses.
  • A recursive function invokes itself.
  • A recurrence relation is a relation that is specified using itself.
  • Anything that can be done recursively can be done iteratively and vice versa.
  • If there were a data processing Inquisition programmers would probably be burned at the stake based on a belief or disbelief in recursion.
Advantages:
  1. Code to implement an algorithm can be very succinct.
  2. If an algorithm is specified recursively, in the form of a recurrence
    relation, it is the easiest way to code it.

Disadvantages:
  1. Expensive in CPU time and memory.
Recurrence Relation Example:
n! = n * (n-1) * (n-2).....1 = n * (n-1)!
4! = 4 * 3 * 2 * 1 = 24

Recursive Function Example:
A translation of the recurrence relation into C++.
int RcrsFact(int Num)
{
if (Num == 0) return 1;
else return (Num * RcrsFact(Num - 1));
}

Example using recursion: Fibonacci Numbers

Fibonacci
a. Real Name: Leonardo of Pisa
b. Fibona cci sh ort for: Filius Bon Acci, or good son of Acci.
c. Well traveled merchant with extensive acquaintance with Mideast
d. Familiar with Arabian mathematics.
e. Introduced European world to Arabic notations for numerals (as
opposed to Roman numerals) in his book Liber Abaci.


Fibonacci Sequence: Fibon(n) = Fibon(n-1) + Fibon(n-2)
a. Number of leaves on certain plants (assuming that no leaves fall
off) is a Fibonacci number.
b. Fibonacci numbers appear in odd places in series or solutions to
equations.
c. Doubly recursive.

Recursive Logic:
int RcrsFibon(int Num)
{
if (Num == 0) return 0;
else if (Num == 1) return 1;
else if (Num == 2) return 1;
else return (RcrsFibon(Num - 1) + RcrsFibon(Num - 2));
}



Read More