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

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.

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:

**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:

**it have an initial condition --> t(0) = 0****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)**