Recursion and Dynamic Programming

Six Runs, One Over, How Many Ways?

It's the last over of an IPL run chase. The batting side needs exactly 6 runs to win, and there's no reason to hold back — every ball is about runs, however they come. To keep the counting clean, simplify the scoring shots to the four most common outcomes at the crease: a single (1 run), a double (2 runs), a boundary (4 runs), or a six (6 runs). Threes are famously rare in cricket — they need real pace between the wickets and a fielding side that's a fraction slow, so ignore them for now, along with byes and mishits, and ask a clean question: in how many different sequences of scoring shots can the batting side reach exactly 6 runs?

Try listing them by hand and something becomes obvious fast: six singles in a row is one way; a boundary followed by two singles is another; a single six is another still. The list grows faster than it looks like it should, and keeping track of which combinations are already counted gets error-prone after the first handful. That kind of difficulty — a problem that is really just smaller copies of itself, stacked several layers deep — is exactly what recursion is built to describe, and what dynamic programming is built to compute quickly. This same pattern, a big counting or optimization question that only makes sense once it's seen as smaller copies of itself, is also precisely what shows up over and over on competitive programming judges like Codeforces and CodeChef, usually dressed up in some other story. By the end of this chapter, the answer to the run-chase question falls out of a seven-line table.

What Recursion Actually Is

Recursion is a function that solves a problem by calling itself on a smaller version of that same problem, until the smaller version becomes small enough to answer directly. Every correct recursive function needs two parts: a base case — the smallest input, answered directly with no further calls — and a recursive case — a rule that reduces a bigger input to a smaller one and calls itself to solve it.

The cleanest possible example is the factorial function, n!, the product of every integer from 1 up to n:

function factorial(n) {
  if (n === 0) return 1;          // base case
  return n * factorial(n - 1);    // recursive case
}

Trace factorial(5) and watch what actually happens. Each call is stuck waiting on the call it makes, so the calls pile up — this pile of waiting calls is the call stack — before any multiplication happens at all:

factorial(5)
  = 5 * factorial(4)
  = 5 * (4 * factorial(3))
  = 5 * (4 * (3 * factorial(2)))
  = 5 * (4 * (3 * (2 * factorial(1))))
  = 5 * (4 * (3 * (2 * (1 * factorial(0)))))
  = 5 * (4 * (3 * (2 * (1 * 1))))
  = 120

Count the calls: factorial(5), factorial(4), factorial(3), factorial(2), factorial(1), and finally factorial(0), which hits the base case and ends the chain. That's six calls to compute factorial(5) — one for every integer from 5 down to 0 — so factorial(n) always makes exactly n + 1 calls in total. Nothing here is wasted: every call answers a question no other call has already answered.

Back to the Run Chase

Recursion translates the run-chase question almost word for word. Let waysToScore(target) count the number of scoring sequences that add up to exactly target runs, using shots of 1, 2, 4, or 6. If the target is already 0, there is exactly one way to finish: stop, having already arrived. If the target has gone negative, the shot that just happened overshot, and that whole sequence is invalid. Otherwise, the very next shot is a single, a double, a boundary, or a six, and whatever runs remain after that shot still have to be scored the same way — which is the same problem again, just smaller:

function waysToScore(target) {
  if (target === 0) return 1;   // nothing left to score — one valid way
  if (target < 0) return 0;     // overshot the target — not valid
  return waysToScore(target - 1)
       + waysToScore(target - 2)
       + waysToScore(target - 4)
       + waysToScore(target - 6);
}

This is correct — run it, and waysToScore(6) really does return the exact count of sequences that reach 6 runs. But watch what happens internally. Answering waysToScore(6) needs waysToScore(5), waysToScore(4), waysToScore(2), and waysToScore(0). waysToScore(5) itself needs waysToScore(4) again — a second, completely independent copy of a call already sitting elsewhere in the tree. Unlike factorial, which asked each smaller question exactly once, this recursion asks the same smaller questions over and over. That repetition has a name — overlapping subproblems — and it is exactly why this innocent-looking function is about to get very slow, very fast.

Why It Explodes: The Fibonacci Case

The clearest place to watch overlapping subproblems blow up is the Fibonacci sequence, defined by fib(0) = 0, fib(1) = 1, and fib(n) = fib(n − 1) + fib(n − 2) for every larger n. It has the same shape as waysToScore — recursive calls that branch and reconverge — but with only two branches per call instead of four, so its recursion tree is small enough to draw out completely:

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Trace every call made while computing fib(5), and count how many times each smaller value gets asked for:

fib(5) is called 1 time
fib(4) is called 1 time
fib(3) is called 2 times
fib(2) is called 3 times
fib(1) is called 5 times
fib(0) is called 3 times
                        -----
                 total: 15 calls

Fifteen calls to compute a single-digit answer. fib(3) gets solved from scratch twice; fib(2) three times; fib(1), the cheapest possible non-trivial call, gets made five separate times, each one oblivious to the other four. Scale the input up and this compounds rather than merely adding up: computing fib(20) — a value that is only 6,765 — takes 21,891 separate function calls to produce. Push to fib(30) and the answer is 832,040, but the call count has climbed to 2,692,537 — closing in on 2.7 million calls to produce a six-digit result. The call count grows at essentially the same rate as the Fibonacci numbers themselves: roughly multiplying by the golden ratio, about 1.618, with every step up in n. That is exponential growth, and it is why naive recursive Fibonacci — and by the same logic, the naive waysToScore — becomes unusable well before n reaches the sizes real programs need to handle. Notice what made factorial different: its calls form a single chain, never branching, so there was never a repeated question to begin with. The blowup here is not a tax on recursion in general — it is specifically the cost of solving the same subproblem again and again.

Memoization: Remember What You've Already Solved

The fix follows directly from naming the disease. If fib(3) is going to be asked for five separate times, the waste is not in the asking — it is in solving it fresh every single time. Memoization keeps a cache of every subproblem's answer the first time it is computed, so every later call for that same subproblem just reads the cache instead of recursing again. This is also called top-down dynamic programming: it still starts from the original question and works its way down toward the base cases, just with a cache riding along for the trip:

function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];   // seen this exact call before — reuse it
  if (n <= 1) return n;            // base case
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

The memo = {} default parameter matters here: JavaScript creates a fresh, empty object every time fibMemo(n) is called without a second argument, so a new top-level call always starts with a clean cache, while the recursive calls inside — which explicitly pass memo along — all share that one cache for the whole computation.

Trace fibMemo(5) and the difference from the naive version shows up immediately:

fibMemo(5)                     [not cached yet — compute]
  fibMemo(4)                   [not cached yet — compute]
    fibMemo(3)                 [not cached yet — compute]
      fibMemo(2)                [not cached yet — compute]
        fibMemo(1) = 1          [base case]
        fibMemo(0) = 0          [base case]
      fibMemo(2) = 1            [store in cache]
      fibMemo(1) = 1            [base case again — trivial, never cached]
    fibMemo(3) = 2              [store in cache]
    fibMemo(2) = 1              [CACHE HIT — returns instantly]
  fibMemo(4) = 3                [store in cache]
  fibMemo(3) = 2                [CACHE HIT — returns instantly]
fibMemo(5) = 5                  [store in cache]

Count every line and the total is nine calls, against fifteen for the naive version. Four values end up stored in the cache — 2, 3, 4, and 5; 0 and 1 are cheap enough that the function just returns them directly every time they're asked for, without ever touching the cache. Each distinct subproblem from 2 up to n is solved exactly once, which is why the savings only grow with n: computing fibMemo(30) takes exactly 59 calls, not 2,692,537.

Tabulation: Build the Table Bottom-Up

Memoization still recurses — it just refuses to repeat work. Tabulation, also called bottom-up dynamic programming, skips the recursion altogether: start from the base case and build every later answer up from smaller ones already sitting in a table, in order, inside a plain loop.

Apply that to the run-chase question directly. Build an array dp where dp[runs] holds the number of ways to score exactly runs more runs. dp[0] is 1 by definition — there is exactly one way to score zero more runs: stop. Every later entry adds up contributions from each shot that doesn't overshoot it:

function waysToScoreTab(target) {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;
  for (let runs = 1; runs <= target; runs++) {
    for (const shot of [1, 2, 4, 6]) {
      if (runs - shot >= 0) {
        dp[runs] += dp[runs - shot];
      }
    }
  }
  return dp;
}

Run it out to target = 6 and read the table straight through:

dp[0] =  1
dp[1] =  1
dp[2] =  2
dp[3] =  3
dp[4] =  6
dp[5] = 10
dp[6] = 19

Every entry is the sum of up to four earlier entries — whichever ones are reachable by subtracting 1, 2, 4, or 6 from the current row. Look closely at how the boundary and the six enter the picture, because it is easy to mix them up. dp[4] sums exactly three terms: dp[3] + dp[2] + dp[0] — the shot-of-6 term is skipped completely, because 4 − 6 is negative. That dp[0] term arrives by subtracting a 4: hit one boundary, and the target is already met, with nothing left to score — exactly one sequence, matching dp[0] = 1. dp[5] also sums three terms — dp[4] + dp[3] + dp[1] — and still no six, since 5 − 6 stays negative. The six only earns its place once the row itself reaches 6: dp[6] = dp[5] + dp[4] + dp[2] + dp[0], and that final dp[0] term is now the six's doing — the single sequence that is just one six, with nothing more to score.

It is worth checking dp[5] = 10 by hand, sorted by how many balls each sequence takes: five singles in a row is one sequence; a single double mixed among four balls of singles can sit in any of four positions, giving four sequences; two doubles mixed with one single among three balls gives three sequences, depending on where the single lands; and a boundary paired with a single, in either order, gives two more. That's 1 + 4 + 3 + 2 = 10 — the same answer the table gives, reached by counting the sequences directly instead of summing the recurrence.

And there is the run chase, answered: dp[6] = 19. There are nineteen different sequences of scoring shots that add up to exactly 6 runs in that final over. The naive recursive version would reach the same number only after making dozens of repeated calls, even for a target this small; the tabulated version gets there by filling seven array slots, each one a handful of additions. Push the target up to, say, 60 runs off the last five overs, and the naive recursion's cost would explode the way fib's did — while the table only grows one slot at a time, linear instead of exponential.

Memoization and tabulation always compute the same answers, but they are not identical in cost. Memoization only ever computes the subproblems actually needed to answer the original call, which matters when large parts of a table would otherwise go unused. Tabulation computes every entry up to the target unconditionally, but it never grows the call stack, which matters once n gets large enough that a purely recursive approach would run out of stack space before it runs out of time. For a problem like waysToScore, where every smaller value from 0 up to the target genuinely is needed along the way, the two approaches end up doing essentially the same amount of work — the choice between them comes down to whether a recursive or an iterative style fits the problem being solved more naturally.

Two More Problems, the Same Idea

Recursion combined with overlapping subproblems shows up constantly once it's recognizable, and two problems in particular are as standard in competitive programming as Fibonacci itself. Both qualify for dynamic programming because they share the same two properties: overlapping subproblems, the repeated-question trouble already seen twice above, and optimal substructure — a guarantee that the best overall answer can always be assembled from the best answers to its smaller pieces, so nothing is lost by solving each piece once and reusing it.

The longest common subsequence (LCS) problem asks: given two sequences, what is the longest sequence of elements that appears in both, in the same relative order, though not necessarily consecutively? It is the idea underneath source-control diff tools and DNA sequence alignment in bioinformatics, and it shows up in fuzzy text matching too — for instance, matching a search query against records filed under an older spelling. Bengaluru was known as Bangalore before its official renaming in 2014, and the two spellings still overlap heavily letter by letter: BENGALURU and BANGALORE share BNGALR in order, a common subsequence of length 6 out of 9 letters each. The recurrence compares the strings position by position: if the current characters match, extend the best answer found one step back on both strings; otherwise, take whichever of "drop the last character of the first string" or "drop the last character of the second string" gives the longer result:

function lcsLength(a, b, i = a.length, j = b.length) {
  if (i === 0 || j === 0) return 0;
  if (a[i - 1] === b[j - 1]) {
    return lcsLength(a, b, i - 1, j - 1) + 1;
  }
  return Math.max(lcsLength(a, b, i - 1, j), lcsLength(a, b, i, j - 1));
}

Solved exactly as written, this recursion branches at every mismatched pair of positions — exponential again, for the same reason waysToScore was. Tabulated as a two-dimensional grid, one row per position in the first string and one column per position in the second, it runs in time proportional to the product of the two lengths: a grid of about a hundred cells for two nine-letter strings like these, instead of an exponential tree.

The 0/1 knapsack problem asks: given a set of items, each with a cost and a value, and a fixed budget, which subset of items — taking each one whole or not at all — maximizes total value without exceeding the budget? It is exactly the problem an IPL franchise faces while filling the last few slots on its roster. Imagine, hypothetically, a franchise with ₹13 crore left in its purse and four shortlisted players costing ₹8 crore, ₹6 crore, ₹4 crore, and ₹5 crore, with projected impact scores of 50, 40, 25, and 35. For each player, the recurrence considers two choices: skip them, carrying forward the best value achievable from the remaining players at the same budget, or buy them, adding their value to the best answer for the remaining players at the budget reduced by their cost — and dynamic programming keeps only the better of those two choices at every step, for every possible budget along the way. For this shortlist, the best combination turns out to be the ₹8-crore and ₹5-crore players together: exactly ₹13 crore spent, for a combined impact score of 85, better than any other affordable combination of the four.

Both problems are common enough in competitive programming that recognizing the shape immediately is worth real practice: two indices walking down two sequences, one step at a time, is almost always some flavor of LCS; an item-by-item either-or choice under a shared limit — weight, budget, time — is almost always some flavor of knapsack. Spotting the shape is most of the battle; writing the recurrence, and then tabulating it, is the easy part once the shape is clear.

From One Over to Every System That Counts Fast

The run-chase question that opened all this turned out to have a precise, provable answer — 19 — and the path to it is the same path fib, LCS, and the knapsack all took: write the recursive definition first, because it is usually the most natural way to describe a problem exactly as stated; notice when the recursion tree revisits the same smaller question more than once; then either cache those answers on the way down, which is memoization, or build them up from the base case in a loop, which is tabulation. The same shape sits underneath far more than cricket puzzles and classroom problems. A fantasy-sports app updating a live win probability after every ball, a UPI app scoring a transaction for fraud risk in the time it takes to blink, a train-booking search comparing thousands of possible seat and route combinations, a maps app choosing the fastest of many possible turns — all of them are, underneath, weighing the exact choice worked through above: recompute the same subproblem endlessly, or solve it once and remember the answer. Recursion states what the answer to a problem is, in terms of smaller versions of itself. Dynamic programming is simply the discipline of making sure a computer only has to work that out once per subproblem — not once for every path that happens to pass through it.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind recursion and dynamic programming, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.