Tutorial for Module 3

This tutorial works through four small problems: Fibonacci (naive and linear-time), testing whether a number is a power of two, fast integer power (by square-and-multiply), and digit-counting. None are individually hard; the point is to consolidate the techniques from Module 3 (recursion, tail calls and accumulators, local helpers) and to make explicit the choice between naive recursive and tail-recursive implementations.

The general rule of thumb: write the naive recursive form first. It is almost always the clearest expression of the algorithm and it is what you should reach for in a sketch or a small script. If the function will be called on large inputs (long lists, large numbers, in hot paths), convert to tail-recursive form using the accumulator pattern from the tail-recursion lecture. Most code never needs the conversion; practitioners get a feel for which functions are likely to be called on big data and rewrite those preemptively.

Problem 1: Fibonacci, naively

The Fibonacci numbers are defined by F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n >= 2. The natural recursive translation:

The function is correct and the code reads exactly like the mathematical definition.

The trouble is performance. Each call to fib n (for n >= 2) makes two recursive calls. So the work to compute fib n is proportional to the number of nodes in a binary call tree of depth n, which is exponential. Specifically, the number of function calls to compute fib n is roughly phi^n where phi = 1.618... is the golden ratio. So fib 30 does about a million calls (takes under a second), fib 40 does about 150 million calls (takes several seconds), fib 50 does about 20 billion calls (takes minutes). The naive fib is unusable for any n past 40 or so.

Why is naive Fibonacci so slow?

The cause is overlapping subproblems. When fib 5 computes `fib 4

• fib 3, the call to fib 4itself computesfib 3 + fib 2. So fib 3is computed *twice* (once directly, once insidefib 4). fib 2is computed three times,fib 1five times,fib 0` three times. The deeper the recursion, the more redundant work.

The fix is to compute each value only once and feed it forward. The cleanest way in a pure-functional style is to carry the last two values as an accumulator pair and update them as you go:

fib 46 now returns 1836311903 immediately. (We use 46 rather than 50 because the in-browser int is 32-bit and fib 47 already overflows it; fib 46 is the largest Fibonacci that fits. On a native 64-bit OCaml, fib 50 = 12_586_269_025 fits fine.) The trick: the accumulator holds two values rather than one. At each step, a is fib k and b is fib (k+1). The recursive call advances both: the new a is b (the previous fib (k+1)), the new b is a + b (the next Fibonacci number, by the recurrence).

The two-accumulator trick is the canonical way to make Fibonacci fast. It works for any recurrence that depends on the last k values: keep a window of those values as the accumulator. Many common sequences (Lucas numbers, Padovan numbers, etc.) yield to the same shape. The general technique of caching intermediate results is called memoisation; we will see it more thoroughly when we get to mutable state in Module 7.

This fib is also tail-recursive (the recursive go call is the last thing in the else-branch), so it runs in constant stack space. You can call fib 1_000_000 without blowing the stack, although the result is a number with hundreds of thousands of digits and would overflow OCaml's native int long before that.

Problem 2: is it a power of two?

A positive integer is a power of two (1, 2, 4, 8, ...) exactly when repeatedly halving it lands on 1 without ever passing through an odd number bigger than 1. The recursion: 1 is a power of two (2^0); an even number is a power of two iff its half is; everything else (zero, negatives, odd numbers above 1) is not.

Trace the two calls: is_power_of_two 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1 -> true; is_power_of_two 96 -> 48 -> 24 -> 12 -> 6 -> 3, and 3 is odd -> false.

Three things to notice. First, the function is already tail-recursive without any rewriting. The recursive call is the final expression of its branch; there is no work after it. No accumulator is needed because the answer needs no combining on the way back up; the base case is the answer.

Second, termination: n / 2 < n whenever n >= 2, and the only inputs that reach the recursive call satisfy n >= 2 (the two base tests have already filtered out everything below 2 and the odds). The argument strictly decreases toward the base cases, and the recursion is at most log2 n deep.

Third, the order of the tests matters. 1 is odd, so if the n mod 2 = 1 test ran first, the function would return false on 1; and since every successful chain of halvings bottoms out at 1, it would then return false on every input. When base cases overlap with a catch-the-rest test, the base cases must come first.

Problem 3: fast integer power

The naive power we wrote in the recursion lecture takes n recursive calls to compute x^n:

For n = 1_000_000, that is a million calls. We can do much better by halving the exponent at each step instead of decrementing. Two cases on the parity of n:

• n even: x^n = (x^(n/2))^2. One recursive call.
• n odd: x^n = x * x^(n-1). One recursive call, but the new exponent n - 1 is even.

The recursion depth is logarithmic in n, not linear. For n = 1_000_000, the naive power makes a million recursive calls; fast_power makes about forty. The transformation is purely algorithmic: same answer, far fewer calls. The trick ("decompose by parity") is the same one that underlies fast matrix exponentiation, modular exponentiation in cryptography, and many related algorithms.

A nuance worth flagging: fast_power is not tail-recursive. The even case has half * half running after the recursive call, and the odd case has x * running after. The accumulator pattern from the tail-recursion lecture does not unfold cleanly here: the running result depends on values you do not know yet. For typical exponents (n up to a few thousand), the logarithmic depth is comfortably small (under 20 frames for n up to a million), so non-tail recursion is fine.

When naive recursion is fine

A pragmatic note: not every recursive function needs to be tail-recursive. If the input is bounded (you know n is at most a few thousand, or the list has at most a few hundred elements), the naive recursive form runs in plenty of stack and reads cleaner. The extra clarity of let rec sum xs = match xs with | [] -> 0 | x :: rest -> x + sum rest over the accumulator form is real, and worth the constant-factor stack use when stack use is not a problem.

Tail recursion matters when:

• The input might be very large: lists with millions of elements, numeric arguments in the millions, recursion that walks deep trees.
• The function is called frequently and you want it cheap on any input.
• You are writing library code others will call with unknown-sized inputs.

For one-off computations on small data, write the natural recursive form and move on. You can rewrite to tail-recursive later if a profiler or a stack overflow tells you to.

Problem 4: counting digits

The number of digits in a non-negative integer is the number of times you can divide it by 10 before reaching zero. The natural recursion:

The recursion strips one digit per step. The base case is "a single-digit number" (n < 10), which catches both 0 through 9 and recursive calls when the remaining n is below 10.

A subtle bug: negative inputs do not terminate cleanly. OCaml's / truncates toward zero, so (-12345) / 10 is -1234 (not -1235). The base test n < 10 is true for all negatives, so the recursion returns immediately with 1, which is wrong. Even worse, with a different base test like n = 0, you would get an infinite recursion. The defensive version uses abs:

This strips the sign at the outermost call; the helper go only ever sees non-negative inputs. The pattern (a defensive outer function plus a local helper that handles only the well-behaved case) is one we will see again. The helper is local because nobody outside count_digits needs it; the outer function is the API.

Note that count_digits 0 returns 1, which matches the convention that the integer 0 has one digit (the digit 0). If you wanted a different convention you would adjust the base case.

A quick check

Activity: sum of digits

Try this before reading the solution. The shape mirrors count_digits: strip one digit per step. The base case is n = 0: an empty number has digit sum 0. The recursive case takes the last digit (n mod 10) and adds it to the digit sum of the rest (n / 10).

The recursion uses two integer operations students have already seen: n mod 10 peels off the last digit, n / 10 shifts the number one place right. After enough steps n reaches 0 and the recursion ends. As with count_digits, the function misbehaves on negative inputs because of OCaml's truncate-toward-zero division; wrap with abs if you want the convention sum_digits (-12) = 3.

A small code challenge

let is_prime n =
  if n < 2 then false
  else
    let rec try_divisor k =
      if k * k > n then true
      else if n mod k = 0 then false
      else try_divisor (k + 1)
    in
    try_divisor 2

What you should be able to do now

By the end of Module 3 you can:

• Define a function with let, anonymous-function form fun x -> ..., or the curried multi-argument form let f x y z = ....
• Read function types: int -> int -> int is right-associative, meaning int -> (int -> int). A multi-argument function is really a function of one argument returning a function.
• Partially apply a curried function: add 5 is a function value.
• Write recursive functions with let rec, in their natural inductive form (base case plus recursive case that reduces toward it).
• Convert a non-tail-recursive function to tail-recursive using an accumulator parameter.
• Use local helpers via let rec go ... in ... and write mutually recursive functions with let rec ... and ... = ....

Module 4 turns to data types: tuples, records, and variants (the algebraic data types that distinguish ML-family languages from mainstream OOP). Pattern matching, which we have previewed all through Module 3, takes centre stage in Module 5.

Reading

• Cornell CS3110, Recursion examples: the textbook's worked examples, with more variations on the patterns above: https://cs3110.github.io/textbook/chapters/basics/functions.html
• Real World OCaml, Lists and Patterns: the corresponding chapter, with a heavy emphasis on the list-recursion idioms: https://dev.realworldocaml.org/lists-and-patterns.html

Sources

This lecture's prose, worked examples, and quizzes are original to this course. Materials referenced during preparation are listed in the Reading section above; Cornell CS3110 and Real World OCaml are CC BY-NC-ND-licensed and have not been derivatively reused. See LICENSES.md at the repository root for the full source posture.