Practice question · Put in order
Order the steps of evaluating a recurrence by unfolding it.
- Add that new term to the list of known terms
- Stop once the term you were asked for has been reached
- Read off the initial conditions, which give the earliest terms outright
- Apply the recursive rule to the known terms to obtain the next term
- Repeat the rule, each time using the terms just computed
Hints
- Nothing can be computed until there is something to compute from.
- The rule always looks backwards, so the sequence has to be built forwards.
Show the answer
- Read off the initial conditions, which give the earliest terms outright
- Apply the recursive rule to the known terms to obtain the next term
- Add that new term to the list of known terms
- Repeat the rule, each time using the terms just computed
- Stop once the term you were asked for has been reached
Why
Unfolding runs forward from the initial conditions, each new term built from ones already known. Without the initial conditions there is nothing to start from and the recurrence defines no particular sequence at all, exactly like a recursive function with no base case.
Practise Recurrence Relations
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.