15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 8 of 12 in the free DSA Basics course · 6 lessons
Write and evaluate recursive functions. You will:
The lesson starts with one numeric function and extends the same ideas to branching calls, tail-recursive helpers, linear inputs, and caching.
None.
You should be comfortable reading simple functions, parameters, return values, conditionals, and arithmetic. You do not need prior recursion experience.
Use sumTo(3), where sumTo(n) returns the sum of every integer from 1 through n.
Its contract is:
n1 + 2 + ... + nsumTo(0) = 0A recursive definition is:
1sumTo(0) = 0
2sumTo(n) = n + sumTo(n - 1), for n > 0Tracing sumTo(3) has two directions:
sumTo(3) needs 3 + sumTo(2).sumTo(2) needs 2 + sumTo(1).sumTo(1) needs 1 + sumTo(0).sumTo(0) reaches the base case and returns 0.sumTo(1) returns 1 + 0 = 1.sumTo(2) returns 2 + 1 = 3.sumTo(3) returns 3 + 3 = 6.Each call changes n to n - 1. The calls reach sumTo(0), then each waiting call uses its returned value.
Recursive Function Design introduces a function that invokes itself on a smaller instance.
Base and Recursive Case defines the two parts of a terminating recursive function before later examples.
Recursion Tree Analysis counts calls, base cases, and returns.
Tail Recursion identifies calls that have deferred work and calls whose recursive call is the final action.
Recursive Traversal of Arrays and Strings applies the design and tracing steps to linear inputs.
Memoization Introduction identifies repeated subproblems in recursion trees and caches their results.
Recursive Function Design defines what a recursive function returns and which smaller input it passes to itself. For sumTo(n), the smaller problem is sumTo(n - 1).
Base and Recursive Case explains the stopping condition and the progress step. sumTo(0) supplies an answer without another call. The recursive case reduces n. A recursive case that calls sumTo(n) again does not move toward 0, so it never terminates. Omitting the base case allows calls to continue until the runtime exhausts the call stack.
Recursion Tree Analysis counts work and separates two measures:
sumTo(n) makes one smaller call at each step. Naive Fibonacci has two calls from each non-base call. Its recursion tree contains repeated subproblems and more total work.
Tail Recursion changes the shape of sumTo. In the original form, each call waits to add its number after the deeper call returns. A tail-recursive helper carries the partial sum in an accumulator, and its recursive call is the final action. The deferred addition moves into the accumulator update. Source code written with tail recursion can still use O(n) stack space if the runtime does not optimize tail calls.
Recursive Traversal of Arrays and Strings uses an index as the progress measure. A function moves an index from the start of an array or string toward its length. Check the stopping condition before accessing an element or character. That order handles empty inputs safely. Traversal reads the input and does not mutate it.
Memoization Introduction identifies repeated Fibonacci calls such as fib(2). Storing a result by its input prevents recomputation. For Fibonacci inputs from 0 through n, the cache stores at most one result for each input. Memoization reduces the work to O(n) time and uses O(n) auxiliary space for the cache, alongside the recursive call stack.
Write the contract for sumTo(n) and identify its input, output, smallest valid input, base case, and smaller subproblem.
Trace sumTo(3) on paper. Write every call down to sumTo(0), then write every return value back up. Do not treat a recursive call as having its answer before it returns.
Test termination changes. Compare sumTo(n - 1) with an incorrect recursive call such as sumTo(n). State exactly why one reaches the base case and the other does not.
Draw the small recursion tree for naive fibonacci(4). Count calls to the same input, especially repeated calls such as fibonacci(2), and compare total nodes with maximum depth.
Rewrite the running example with an accumulator, such as sumTail(3, 0). Trace how the accumulator changes at each call, then note whether your runtime guarantees tail-call optimization.
Practice index-based recursion on a small array such as [4, 1, 3]. Start at index 0, move forward one index per call, and stop when the index equals the array length. Repeat with a string and count a chosen character.
Return to fibonacci(4) and add a cache. Mark each call as a cache miss when it must compute a result or a cache hit when it reuses one. Then compare the uncached recursion tree with the memoized version.