Consider the recursive function Fibonacci, how many function calls are made for each level of recursion? Solution: each level of recursion in the Fibonacci function has a doubling effect on the number of calls. The number of recursive calls that will be executed to calculate the n^th Fibonacci number is on the order of 2ⁿ. Calculating the 20^th Fibonacci number would require on the order of 2²⁰ or about a million calls, calculating the 30^th Fibonacci number would require on the order of 2³⁰ or about a billion calls. Computer scientists refer to this as exponential complexity. So problems with exponential complexity can quickly overwhelm even the largest super computers. An explicit formula would resolve the need for so many function calls.

The most basic method for finding an explicit formula for a recursively-defined sequence is iteration. Iteration works as follows: Given a sequence a₀, a₁, a₂, … defined by a recurrence relation and initial conditions, you start from the initial conditions and calculate successive terms of the sequence until you see a pattern developing. At that point you guess an explicit formula.

Any problem that can be solved recursively, can be solved iteratively (nonrecursively). A recursive approach is normally chosen in preference to an iterative approach when the recursive approach more naturally mirrors the problem and results in a program that is easier to understand and debug. Another reason to choose recursive solutions is that the iterative solution may not be apparent. Recursion must be avoided in cases of exponential complexity unless strict restraints are placed on the number of recursions allowed; i.e. the problem is kept very small.

Definition A sequence a₀, a₁, a₂,… is called an arithmetic sequence if, and only if, there is a constant d such that

a_k = a_k - 1 + d for all integers k ³ 1.

Definition A sequence a₀, a₁, a₂,… is called a geometric sequence if, and only if, there is a constant r such that

a_k = r × a_k - 1 for all integers k ³ 1.

Useful formulas:
Sum of a Geometric Sequence: (r not equal to 1)

Using iteration to find a formula for the Towers of Hanoi problem 

Checking Correctness of the Solution to a Recurrence Relation (a Geometric Series) using Mathematical Induction