Recurrence Relations: Lesson
Lesson 1 of 1
  1. 1
    Review of Recursion
    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…
    Start
  2. 2
    Review of Dynamic Programming
    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…
    Start
  3. 3
    Linear Recurrence
    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…
    Start
  4. 4
    Closed-Form Solution
    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…
    Start
  5. 5
    Closed-Form Solution (Repeated Roots)
    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 …
    Start
  6. 6
    Solutions of Inhomogeneous Recurrence Relations
    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}…
    Start
  7. 7
    Review
    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…
    Start

How you'll master it

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