Skip to main content

Courses About Pricing Educators

Sign in Get started

Courses About Pricing Educators

Get started Sign in

Loading courses

Loading lessons

Recursion and Divide and Conquer: Data Structures and Algorithms: Uncharted

Courses Data Structures and AlgorithmsRecursion and Divide and Conquer

Recursion and Divide and ConquerPro

Use base cases, smaller calls, and balanced halves to control recursive work.

Data Structures and Algorithms
Unit 6 of 16
20 lessons
128 min
420 XP

This unit is part of Pro. Upgrade to open every lesson in it.

Lessons

20 total

1Mirrors in MirrorsIdentify the shrinking subproblem and reachable base case that make a recursive definition terminate.ProInteractiveConcept6 min20 XPOpen
2The Call Stack, AgainApply entry-before-call and exit-after-call tracing to printing entry before a smaller call and exit after it.ProCodeConcept6 min20 XPOpen
3Sum, Split in HalfApply recursive half-sum divide to summing two recursive halves.ProCodeConcept6 min20 XPOpen
4Count the CallsApply naive branching recursion instrumentation to measuring the branching explosion of naive Fibonacci.ProCodeConcept6 min20 XPOpen
5Draw the Call TreeRepresent fib(4) as one node per invocation, including separate nodes for repeated argument values.ProDiagramConcept6 min20 XPOpen
6Base Cases FirstDiagnose missing or misplaced base cases by testing each recursive definition's smallest valid inputs.ProInteractiveConcept6 min20 XPOpen
7Max by TournamentApply pairwise half-tournament maximum to comparing winners from pairwise halves.ProCodeConcept6 min20 XPOpen
8Guess by HalvingApply ordered range halving to narrowing an ordered range after each guess.ProCodeConcept6 min20 XPOpen
9Merge, PreviewedApply two-pointer merge of divided halves to zipper-merging two sorted halves.ProCodeConcept6 min20 XPOpen
10Halves All the Way DownDerive O(n log n) when logarithmically many split levels each perform n total merge work.ProInteractiveConcept6 min20 XPOpen
11Power in Log StepsApply exponentiation by squaring to halving an exponent and squaring the half result.ProCodeConcept6 min20 XPOpen
12The Recursion LimitApply language-specific recursion failure followed by an explicit-stack rewrite to observing JavaScript RangeError versus Python RecursionError, then rewriting the traversal with an explicit stack.ProCodeConcept6 min20 XPOpen
13Flatten the NestedApply recursive nested-list flattening to recursing into nested lists and collecting leaves.ProCodeConcept6 min20 XPOpen
14Digital RootApply recursive digit reduction to reducing digit sums until one digit remains.ProCodePractice8 min20 XPOpen
15Hanoi, LiteApply recursive move-around-smaller Hanoi decomposition to moving smaller towers around one largest disk.ProCodeConcept6 min20 XPOpen
16Divide or Iterate?Choose recursion, divide and conquer, or iteration from problem shape and maximum call depth.ProInteractiveConcept6 min20 XPOpen
17All the Bit StringsApply recursive binary choice generation to branching on 0 or 1 until the target length.ProCodePractice8 min20 XPOpen
18Predict the RecursionPredict recursive entry and exit order by locating work before and after the smaller call.ProInteractiveConcept6 min20 XPOpen
19Cost of the SplitClassify recursive costs from branch count, shrink rate, combine work, and depth.ProInteractiveConcept6 min20 XPOpen
20Recursion Mastery CheckApply divide-to-sum plus logarithmic power synthesis to combining recursive halves with logarithmic exponentiation.ProCodeMastery check10 min40 XPOpen

Stacks and Queues Sorting