# Recurrence Relations

Learn about recurrence relations.

StartRecurrence Relations: Lesson

Lesson 1 of 1

- 1As you learned in your Data Structures and Algorithms course, a recursive function is a function that computes a value by making a call to itself. This implies that a recursive function uses previo…
- 2Recall, the recursive function for calculating the *n th * term of the Fibonacci sequence exhibits an algorithmic runtime complexity that is exponential; this means that as the input grows, the tim…
- 3In this lesson, we will explore
*linear recurrence relations*. A*linear recurrence relation*is a recurrence relation that comes in the form: a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k… - 4Computing the first few terms of any recurrence relation is fairly easy to do by hand; however, finding larger terms is impractical. It would be nice if we had some mathematical function in which w…
- 5In the previous exercise, we learned how to obtain the closed-form solution for a recurrence relation whose characteristic equation had real and distinct roots. In this exercise, we will learn how …
- 6Until now, we have learned how to handle recurrence relations that are homogenous. In this exercise, we are going to take a look at recurrence relations that come in the form of: a_n = c_1 a_{n-1}…

## How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory