UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 8.3 Free with a free account
Calculating the True Cost of Methods That Call Themselves
Data Structures and Algorithms · Chapter 8: RecursionSection 8.3 · lesson 33 of 8711 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Self-Calling Techniques for Complex Structures →← Thinking RecursivelyNext lesson: Self-Calling Techniques for Complex Structures →
In this lesson
Recurrences, recursion trees, the master theorem, and memoization.
- Write a recurrence relation from a recursive method's base case, calls, and extra work
- Solve recurrences by unrolling, recursion trees, substitution, and the master theorem
- Distinguish a recursive method's running time from its stack space
- Apply memoization to remove redundant recursive calls
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,791 words). Read along, or search it.
Opening Question
The Hidden Cost of Self-Calls
For a loop, cost is easy to read off the code: count the passes, and the work in each pass. A method that calls itself hides its cost. The body may look tiny, yet it starts two more calls, and each of those starts two more. Fib of forty, written the obvious way, makes over three hundred thirty-one million calls. Before this lesson ends, the same answer will take seventy-nine. Two resources matter, and they behave differently. Time depends on the total number of calls. Space depends on how many calls are waiting at the same moment.
Definition
Writing a Recurrence Relation
To measure it, write the cost as a formula. Let T of n be the number of steps a method takes on an input of size n. A recurrence relation gives T of n in terms of T of smaller sizes. You read it straight from the method, with three questions. Base case: what does the smallest input cost? Usually a fixed amount. Calls: how many recursive calls does one call make, and how big is each one? And extra work: what happens outside those calls, such as a loop, a comparison, or combining the results?
Worked Example
Subtracting Versus Halving
Two small methods show the idea. Sum to n adds n to the sum up to one less than n. Halvings counts how many times n can be halved. Both make one call, and do a constant amount of other work. So sum to n costs T of one less than n, plus a constant c. And halvings costs T of half of n, plus c. The only difference is how fast the input shrinks. As you'll see, that difference decides everything.
Overview
Three Tools for Solving Recurrences
A recurrence is only a description. Solving it means finding a formula with no T on the right-hand side. Three tools do the job. A recursion tree draws every call, writes the work of each, and adds up the cost level by level. It shows where the work happens. Unrolling substitutes the formula into itself, again and again, until the base case appears. It suits inputs that shrink by subtraction. And substitution guesses the answer, then checks the guess with a base case and a step. It turns a good guess into a proof.
Recursion Tree
Every Level of the Tree Costs n
Start with the tree, for T of n equals two T of n over two, plus n: two calls on halves, and a loop over n items. The top call does n work. It makes two calls on halves, each doing n over two, so that level also costs n. The next level has four calls, each a quarter of the size. Again, n. Every level costs n. Halving n down to one takes log base two of n steps, so there are log n plus one levels. The total is n times that: order n log n.
Unrolling
Substituting the Formula into Itself
When there's only one call, unrolling is easier. Take T of n equals T of one less than n, plus c. Replace the inner T by its own formula, and you get T of n minus two, plus two c. Do it again, and it's T of n minus three, plus three c. After k rounds, it's T of n minus k, plus k times c. The base case appears when k reaches about n, so the cost grows in proportion to n. That's linear. The same steps solve the other shapes. Halving gives log n. A loop over n items in each call gives n squared. Two calls on one less double each round: two to the n.
Substitution
Confirming an n Log n Guess
Substitution confirms a guess. Take the tree's recurrence, with T of one equal to one, and guess that T of n is at most two n log n. Base case: T of two is two times T of one, plus two, which is four. The guess gives two times two times one: also four. It holds. Step: assume the guess holds for n over two. Then T of n is at most two times that bound, plus n, which works out to two n log n, minus n. That's never more than two n log n. Confirmed: order n log n, matching the tree. Substitution can't find the answer for you. A common habit: guess with a tree, then confirm by substitution.
Master Theorem
Comparing d with Log Base b of a
Many recurrences share one form: a method makes a calls, each on an input b times smaller, and does n to the d work outside the calls. The master theorem solves that form. Compare d with log base b of a. If d is smaller, the many small calls at the bottom dominate, and the cost is n to the power log base b of a. If they're equal, the work is spread evenly across all the levels: n to the d, times log n. If d is larger, the top call dominates, and the cost is just n to the d. One limit: the input must be divided by a constant factor. The theorem doesn't apply to recurrences that subtract, like T of one less than n. Unroll those. Try it on three. Two T of n over two, plus n: a and b are two, and d is one. Log base two of two is one, so they're equal: n log n. Four T of n over two, plus n: log base two of four is two, which is bigger than d. The bottom wins: n squared. And three T of n over two, plus n: log base two of three is about one point five eight, so the cost is about n to the one point five eight.
Quick Check
Eight Calls on Halves
Quick check. A method makes eight calls, each on half the input, and does n squared work outside them. What's its cost: order n squared, n squared log n, or n cubed? Pause, and decide. It's n cubed. Here a is eight, b is two, and d is two. Log base two of eight is three, which is bigger than d. So the many small calls at the bottom dominate, and the cost is n to the third. N squared would need the top call to dominate, and with halves and n squared work, that takes fewer than four calls.
Space
Recursion Depth Times Frame Size
Solving the recurrence gives the time: the total work across all calls. Space is a separate question. Each active call gets a stack frame, holding its parameters, its locals, and the place to return to. The frame is freed when its call returns. So the space a recursive method needs is its recursion depth, the longest chain of calls waiting at once, times the size of one frame. Time counts every call. Space counts only the calls that are waiting together.
Comparison
Time Versus Depth for Four Shapes
Put the shapes side by side. One call on one less: time n, depth n, a chain of n waiting calls. One call on half: time log n, and depth log n. Halving shortens the chain quickly. Two calls on halves: time n log n, but depth only log n, because the two calls run one after the other. And two calls on one less: time two to the n, yet depth only n. The first call finishes, and frees its frames, before the second begins. So a method can be hopelessly slow, and still use very little stack.
Common Mistake
Fast Enough but Too Deep
The reverse is a practical hazard. The stack is limited. A method that only calls itself fails after a few tens of thousands of calls, and the exact number varies, even between runs. So a method with depth n can run in good time, and still crash on an input of a hundred thousand. A loop doing the same work uses a constant amount of stack. And memory the method creates, such as a copy of an array in every call, has to be counted separately.
Redundant Calls
Overlapping Subproblems in Fibonacci
Now, redundant calls. Fibonacci's recurrence is T of n equals T of one less, plus T of two less, plus c. In the call tree for fib of five, fib of three happens twice, and fib of two three times. Each repeat redoes all the work beneath it. These are redundant calls, and they happen because the smaller problems overlap. Each step up in n multiplies the calls by about one point six. Fib of thirty makes about two point seven million calls. Fib of forty makes over three hundred thirty-one million.
Memoization
Saving Answers in a Memo Table
The fix is simple: memoization. Keep a table of the answers you've already found. Before computing a value, look it up. After computing it, store it. Then each value is computed only once. Here, a zero in the memo array means not found yet. Fib of five drops from fifteen calls to nine. At forty, it's seventy-nine calls instead of three hundred thirty-one million, and fib of ninety comes back almost instantly. Count the cost directly. There are only n plus one different arguments, each computed once, with constant work. That's order n time. The price is memory: a table of n plus one values, and a stack depth of n. It's the time-space trade-off, applied to recursion.
Decision Guide
When Memoization Helps
Memoization helps when the same arguments come up again and again, and when the result depends only on those arguments. It doesn't help when every call has different arguments, as in sum to n. Or when the result also depends on something that changes. Or when the saved answers wouldn't fit in memory.
Quick Check
Climbing Stairs with Saved Answers
One more check. This method counts the ways to climb n stairs, taking one or two steps at a time. Now give it a table of saved answers. How many calls does ways of n make: about n, about n squared, or about two to the n? Pause, and decide. About n. Ways makes two overlapping calls, just like Fibonacci, so without a table its calls multiply exponentially. But only about n different arguments ever occur: n down to zero, plus minus one. With a table, each is computed once, so the time is order n, for order n extra memory. Two to the n is the cost without saved answers.
Key Takeaways
Recursive Cost Essentials
To sum up. Read a recurrence from the method: the base case, the calls, and the extra work. Unroll recurrences that subtract, draw a tree to see where the work is, and confirm a guess by substitution. The master theorem solves dividing recurrences, by comparing d with log base b of a. Time counts every call, and space only the deepest chain. And memoization trades memory for time.
Think About It
Two Halves and Fixed Work
Something to think about. A method splits its input into two halves, calls itself once on each half, and does a fixed amount of other work. Would you expect its stack to be deep or shallow? And its time closer to n, or to n squared? Draw three levels of its tree to check.
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Calculating the True Cost of Methods That Call Themselves
What is a recurrence relation in algorithm analysis?
How do you use the master theorem?
How much stack space does a recursive method use?
What is memoization in recursion?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →