In an Analysis of Algorithm, recurrence relations are used to analyze the running time of a recursive function. The running time of a recursive function is denoted by $T(n)$ where $n$ is the size of the input. In recurrence relation, the running time of a recursive function of input size $n$ is expressed in terms of the running time of the lower value of $n$. For example

$$T(n) = T(n - 1) + O(1)$$

Here, the running time for size $n$ is equal to the running time for size $n - 1$ plus a constant time. Usually, the running time $T(n)$ is expressed as a conditional statement having the following two conditions

**Base Case**: The base case is the running time of an algorithm when the value of $n$ is small such that the problem can be solved trivially.**Recursive case**: The recursive running time is given by a recurrence relation for a large value of $n$.

Using base and recursive case, the running time of a recursive function would look like the following.

$$T(n) = \begin{cases} O(1) & \text{ if } n \le 2 \\

T(n - 1) + O(1) & \text{otherwise}

\end{cases}$$

This recurrence relation can be interpreted as follows - when the value of $n$ is less than or equal to 2, we can find the solution trivially in $O(1)$ time. If the value of $n$ is greater than 2, we can use the recurrence relation to find the running time.

So far we have learned what is recurrence relation and how to represent it in a conditional statement. Next, we will how to write recurrence relation looking at the code. The process of translating a code into a recurrence relation is given below.

- The first thing to look in the code is the base condition and note down the running time of the base condition. Remember: every recursive function must have a base condition.
- For each recursive call, notice the size of the input passed as a parameter.
- Calculate the running time of operations that are done after the recursion calls.
- Finally, write the recurrence relation.

Let us try to translate some code example starting with the factorial function. A C programming code to calculate the factorial of a number $n$ is shown below.

1 | int fact(int n) { |

The base condition happens when the value of $n$ is 0. We can find the value of $0!$ in constant time $O(1)$ trivially i.e. for base condition

$$T(0) = O(1)$$

Next, we look for the recursive call. There is only one recursive call with input size $n - 1$ and after the recursive function returns we do a simple multiplication that takes $O(1)$ time i.e. the total running time is

$$T(n) = T(n - 1) + O(1)$$

Combining this with the base condition, we get

$$T(n) = \begin{cases} O(1) & \text{ if } n = 0 \\

T(n - 1) + O(1) & \text{otherwise}

\end{cases}$$

Let us do another example of calculating n^{th} Fibonacci number. The C code for this is shown below.

1 | int fib(int n) { |

When the value of $n$ is 0 or 1, we can trivially find the corresponding Fibonacci number in constant time i.e.

$$T(n) = O(1) \text{ if } n \le 1$$

There are two recurrence relations - one takes input $n - 1$ and other takes $n - 2$. Once we get the result of these two recursive calls, we add them together in constant time i.e.

$$T(n) = T(n - 1) + T(n - 2) + O(1)$$

Combining with the base case, we get

$$T(n) = \begin{cases} O(1) & \text{ if } n \le 1 \\

T(n - 1) + T(n - 2) + O(1) & \text{otherwise}

\end{cases}$$