Recurrence Relations: Lesson
Lesson 1 of 1
1. 1
As 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…
2. 2
Recall, 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…
3. 3
In 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…
4. 4
Computing 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…
5. 5
In 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 …
6. 6
Until 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}…
7. 7
Great job! You’ve learned a lot about recurrence functions, their applications, and how to solve them. Here’s a brief summary of everything you learned. A recurrence relation is a mathematical eq…

## How you'll master it

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