Fibbonacci number can be calculated with the algorithm that follows. What is the recurrence relation for the number of additive operations done by this algorithm? Be sure to clearly indicate in your answer what you think the direct solution, division of the input and combination of the solutions are.

int Fibonacci( N )

//N the Nth Fibonacci number should be returned

if N == 1 or N == 2 then

return 1

else

value1 = N-1

value2 = N-2

return Fibonacci (value1) + Fibonacci (value2)

end if