Recursion

A recursive function is a function that calls on itself.
A recursive function must contain a decision structure that divides the code into two cases.
- The recursive (general) case.
- The nonrecursive (special) case.
The code must guarantee that eventually the nonrecursive case is called.
Advantages of Recursion
- The code may be much easier to write.
- Some situations are naturally recursive.
Disadvantages of Recursion
- Recursive functions are generally slower than nonrecursive functions.
- Excessive recursion may overflow the system stack.
- One must be very careful when writing recursive functions.
Naturally Recursive Data Structures
- Linked lists.
- Binary trees.
Example - Factorial.cpp
Example - GCD.cpp
Example - BinomialCoefficients1.cpp
Example - BinomialCoefficients2.cpp
Example - TowersOfHanoi.cpp

This page was last modified on Apr 5, 2001

URL: http://people.hsc.edu/faculty-staff/robbk/Coms262/Lectures/Recursion.html