Question

What is the difference between an explicit and recursive formula?

Answer 1

A recursive formula references itself in its definition. For example, the well known Fibonacci numbers are defined by the formula

`F_n = {(0 if n=0), (1 if n=1), (F_(n-2)+F_(n-1) if n>1):}`

Using this definition, if we wanted to find the Fibonacci number `F_5`, we would have to first calculate the ones before it.

`F_2 = F_0+F_1 = 0+1 = 1`
`F_3 = F_1+F_2 = 1+1 = 2`
`F_4 = F_2+F_3 = 1+2 = 3`
`F_5 = F_3+F_4 = 2+3 = 5`

An explicit formula does not reference itself, and can be calculated directly, without applying it more than once. For example, an explicit formula for the Fibonacci numbers is

`F_n = (phi^n-(1-phi)^n)/sqrt(5)` where `phi = (1+sqrt(5))/2`.

Unlike when using the definition, we can use this explicit formula to calculate `F_5` without calculating `F_2, F_3, F_4`.

`F_5 = (phi^5-(1-phi)^5)/sqrt(5) = 5`