Today's mix: Geography, algorithms,....

Recurrence Equation

What is a Recurrence Equation?
it is a mathematical equation where the value of the function at a given n is given in terms of the value of the function in a smaller value of n

recurrence equation is used in algorthmis analysis to represent recursive functions,like a recursive function, a recurrence equation needs an intial condtion where the call stack will stop evenually at.

Example Fabonanci function:


input: non-negative number n
output: n!
Algorthim:
int fact (int n) {
if (n == 0) return 1;
else return n * fact (n - 1);
}
suppose that t(n) is the number of multiplication done for a given value of n:
t(n) = t(n-1) + 1 where n >= 1
t(0) = 0
The above equation is a Recurrence equation it conforms the tow conditions stated in the definition mentioned earlier:

1. it have an initial condition --> t(0) = 0
   
2. the value of the equation at n is in-terms of the value of the same equation with a smaller n (n-1 in out example)