Recursion
- Recursion
- Recursion is defined as: "An expression [or in our case a
function], such that each term of which is determined by application of a
preceding term or terms."
- For example, the Fibonacci sequence is recursive in that the nth
term (called Fn) is based on the sum of the two previous terms
(i.e., Fn-1 and Fn-2): Fn = Fn-1
+ Fn-2
- As with all recursion, you need to "bottom out" somewhere, and so with
the Fibonacci sequence the first two terms are F1 = 1 and F2
= 1
- From these ideas we can compute the nth Fibonacci number with a
recursive program (see fib.cpp).
- For another example of recursion (computing factorials) where n! =
n * n-1! with 0! = 1 (see factorial.cpp).
- Example: exponentials can be defined recursively where be =
b * be-1 with b0 = 1 (see power.cpp)