What is the difference between an explicit and recursive formula?

1 Answer
Jan 8, 2017

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#