Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

8: Recursion and Recurrence Relations

( \newcommand{\kernel}{\mathrm{null}\,}\)

Fibonacci Sequence

Zero, one! One, two, three! Five and eight!
Then thirteen, twenty-one! At this rate
Fibonacci appears;
The man's sequence for years
Has kept math students studying late.

Goldie, The Omnificent English Dictionary in Limerick Form

An essential tool that anyone interested in computer science must master is how to think recursively. The ability to understand definitions, concepts, algorithms, etc., that are presented recursively and the ability to put thoughts into a recursive framework are essential in computer science. One of our goals in this chapter is to help the reader become more comfortable with recursion in its commonly encountered forms.

A second goal is to discuss recurrence relations. We will concentrate on methods of solving recurrence relations, including an introduction to generating functions.


This page titled 8: Recursion and Recurrence Relations is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Al Doerr & Ken Levasseur via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?