UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 8.4 Free with a free account
Self-Calling Techniques for Complex Structures
Data Structures and Algorithms · Chapter 8: RecursionSection 8.4 · lesson 34 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: Checking Every Element One at a Time Until the Target Appears →← Calculating the True Cost of Methods That Call ThemselvesNext lesson: Checking Every Element One at a Time Until the Target Appears →
In this lesson
Recursion on linked lists, folder trees, divide and conquer, and backtracking.
- Write recursive methods that measure, search, and modify linked lists and folder hierarchies
- Explain why divide and conquer saves time only when it avoids repeated work
- Apply backtracking with choose, explore, and un-choose to subsets, permutations, and mazes
- Use pruning to cut branches that cannot lead to a solution
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,667 words). Read along, or search it.
Opening Question
Data That Repeats Its Own Shape
Why do some problems fit a method that calls itself so well? Because the data repeats its own shape. A linked list is a node, followed by a smaller list. A folder holds files, and smaller folders. And a choice among many options is one choice, followed by a smaller set of choices. Before writing such a method, ask four questions. What's the smallest input, and its answer? What one piece of work can I do now? What smaller problem is left? And how do the answers combine?
Worked Example
Length, Sum, and Contains on a List
A list is either empty, null, or a node whose next field leads to another list. That sentence turns straight into code. Length: an empty list has length zero. A longer list is one node, plus the length of everything after it. Next is shorter on every call, so the calls must reach null. Sum and contains follow the same plan. Contains has two stopping points: reaching null, not found, and finding the value. Run it on four, seven, two, nine: length four, sum twenty-two. Two is there, five isn't, and an empty list has length zero.
Trace
Answers Come Back Up the Calls
To see what really happens, this version prints a line when each call starts and when it ends, indented by depth. The calls go down the list until the base case answers zero. Then each waiting call finishes its addition, and hands its answer back up: two, nine, and last, thirteen. No call can finish until the one below it has finished. That's why the answer comes out last.
Key Idea
Printing a List Forward and Backward
Where a statement sits relative to the call decides when it runs. Code before the call runs on the way down, in list order. Code after the call runs on the way back up, in reverse. Forward prints four, seven, two, nine. Backward prints nine, two, seven, four. A singly linked node has no link to the one before it, so this is the simplest way to process a list from the end.
Quick Check
Printing Before and After the Call
Quick check. This method prints a node's value before its call, and again after it. The list is one, two, three. What does it print? Pause, and predict. It prints one two three, three two one. The prints before the calls run on the way down. The prints after them run on the way back, in reverse. The innermost call, for three, finishes first, so its second print comes right after its first.
Modifying Lists
Returning the New Head
A method that changes the list has a problem. If the first node is removed, the caller's variable must point somewhere else. So the method returns the head of the result. Remove first says: keep this node, and let the rest of the list fix itself. When the target is found, returning next skips the node. Remove seven, then four, then five, which isn't there and changes nothing. Then append six at the end. The caller must write list equals remove first. Ignore the returned head, and removing the first node seems to do nothing.
Limitations
Long Lists Exhaust the Stack
Every waiting call takes memory on the call stack, and a list of n nodes needs n waiting calls. Length works on a thousand nodes. On a million, the stack runs out. The try and catch are only there to report it. A plain loop counts a million without trouble. Each node is visited once either way. The difference is space: the loop needs a few variables, the recursion n stack entries. For long lists, use a loop. For hierarchies a few levels deep, recursion is safe.
Hierarchies
Folder Sizes, Counts, and Depth
A folder hierarchy is nested data: a folder holds entries, and any entry can be another folder. Total size returns a file's size, or adds up a folder's contents. A list node has one smaller problem, so one call is enough. A folder can have any number of children, so a loop walks sideways, and the recursion walks downward. Count files and depth use the same pattern, combining differently: adding for the count, and the largest child plus one for the depth. In print, the level grows per step down. Print the sample project: its folders and files, indented by level. It totals ninety-three kilobytes: six files, four levels deep. And src alone is twenty-four.
Searching
Finding a Path and a Hidden Bug
To search, try each child in turn, and stop as soon as one succeeds. Path returns the path to the first entry with a name, or null. A call that comes back null only means, not in that child, so the loop moves on. A non-null result is returned with this folder's name in front. Text dot java and logo dot png are found. Video dot mp4 isn't. Now a bug. Return inside the loop looks harmless, but it stops after the first child. Readme is found, only because it's the first child. Every other search returns project, slash, null. Joining null to a string doesn't fail, which makes this bug easy to miss.
Divide and Conquer
Max of Halves Versus Fast Power
Divide and conquer splits a problem into smaller ones of the same kind, solves each recursively, and combines the answers. Max of halves its range until one item is left, then combines with the larger of two. It finds nine in eight items, but makes fifteen calls. On a thousand items, nineteen ninety-nine. That's two n minus one. A loop also looks at each item once, so splitting saved nothing here. Divide and conquer organizes a solution. It doesn't guarantee speed. Power is different. X to the n is the square of x to the n over two, and that half-size problem is solved once. At a thousand, slow power makes a thousand and one calls, and fast power eleven.
Key Idea
When Splitting Actually Saves Work
So splitting, by itself, saves nothing. Fast power wins because it solves one half, and reuses it. Max of must solve both halves. Binary search keeps one half and discards the other. Merge sort and quicksort solve both halves, and their own lessons later show where their savings come from.
Backtracking
Choose, Explore, Un-Choose for Subsets
Some problems ask for every arrangement. The program builds an answer one decision at a time, and undoes a decision to try the next option. That's backtracking: choose, explore, un-choose. Each item is in or out, so n items have two to the n subsets. Subsets decides one item per call: leave it out, explore; add it, explore, remove it. For one, two, three: eight subsets, and fifteen calls, one plus two plus four plus eight. And save a copy, not the working list. Save cur itself, and every slot refers to the same list. By the end everything's been un-chosen, so all eight come out empty.
Backtracking
Generating Every Permutation
A permutation is one ordering of all the items. At each position the choices are the items not used yet, so a used array records which are taken. Un-choosing means two things: delete the last letter, and mark the item unused again. Run it: three letters give six orderings. Counting both for four to seven items: permutations overtake subsets at four, and pull away. Seven items: a hundred twenty-eight subsets, but five thousand forty orderings.
Quick Check
A Missing Reset of Used
Quick check. This compact version builds each ordering as a new string, so only used needs un-choosing. And the line that resets it is missing. What does it print for A, B, C? Pause, and predict. Only A B C. After the first ordering is recorded, every item stays marked used, so no later choice has a free item. Un-choosing must undo every change that choosing made.
Pruning
Cutting Branches That Pass Fifteen
Often a partial choice can be rejected before it's finished. Find every subset of these numbers that adds up to fifteen. All the numbers are positive, so once the running total passes fifteen, nothing later can bring it back. Cutting that branch off is called pruning. Both runs find the same four answers. Without pruning: five hundred eleven calls. With it: two hundred nine. One line is the whole difference.
Worked Example
Solving a Maze by Backtracking
A maze is the classic picture of backtracking. Choose: mark the current cell with a star, as part of the route. Explore: try the four neighbors, down, right, up, left. The or operator stops at the first one that returns true. Un-choose: if all four fail, it's a dead end, so change its star to an x, and return false, so the caller tries its next direction. Fifty-nine calls find a route. The stars are the route, and the x's are dead ends that were tried. The direction order picks the route, so it isn't necessarily the shortest.
Building Structures
Rebuilding Folders from Paths
Recursion can also build a structure. Suppose data arrives as paths, like src slash util slash text dot java. Add path takes one step per call. The last name is the file itself: the base case. For any earlier name, it finds the folder, or creates it, and recurses one level down. Navigate has the same shape for reading: it follows one name at a time, and returns null as soon as one is missing. The six paths rebuild the same project. Src slash util was created once, and reused. And docs slash video isn't found.
Pattern Summary
Four Jobs, One Skeleton
Four jobs on a hierarchy share one skeleton, with a different base case and a different way to combine. Measuring sums the child answers. Searching returns the first non-null one. Building finds or creates one folder, and recurses into it. Navigating follows one name, and returns what it reaches, or null.
Common Mistakes
Recursion Bugs on Structures
The usual mistakes. No base case for null gives a null pointer exception. A call on the same input, not a smaller one, never ends. Returning inside the loop over children searches only the first child. Saving the working list makes every result identical. Forgetting to un-choose carries stale choices into later branches. And assuming a split always saves time: count the calls.
Key Takeaways
Recursive Techniques Essentials
To sum up. When data repeats its shape, the method can follow it: handle one piece, and recurse on the smaller rest. Work before the call runs on the way down, and work after it on the way back up. Divide and conquer doesn't guarantee savings, so count the calls. And backtracking chooses, explores, and un-chooses, ideally with pruning.
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 Self-Calling Techniques for Complex Structures
How do you find the length of a linked list recursively in Java?
What is backtracking in recursion?
Does divide and conquer always make an algorithm faster?
What is pruning in backtracking?
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 →