Learn/C#/11. Recursion
Lesson 11 of 15
Sign in

C#, lesson 11

Recursion

A recursive method calls itself. Instead of describing every step, you describe how to solve a problem using the answer to a smaller copy of the same problem, and you say what to do when the problem is so small that the answer is obvious.

Base case and recursive case

Every recursive method needs:

  1. A base case: an input small enough to answer directly.
  2. A recursive case: a call to itself with an input closer to the base case, plus a little work to turn that answer into this one.

Factorial(4) needs Factorial(3), which needs Factorial(2), which needs Factorial(1), the base case. Then the results flow back: 1, 2, , .

2 exercises to try what you just read.

Exercise 1

Digital root

Press Ctrl Enter or Check to test your code.

Exercise 2

Tower of Hanoi

Press Ctrl Enter or Check to test your code.

6
24

The call stack

Each call gets its own parameters and local variables, stored in a stack frame. Frames pile up until the base case is reached, then unwind. The stack is limited (about a megabyte by default), so recursion that never reaches its base case, or goes very deep, crashes the process with a stack overflow. In .NET this cannot be caught with try/catch; the program simply ends. That makes two rules important:

  • Every recursive call must move toward the base case.
  • For a simple count over millions of items, use a loop.

Trust the smaller call

The trick to writing recursive code is to assume the call on the smaller input already works, and only ask how to use its result:

Recursion fits problems that look the same at every size: folders inside folders, menus with sub-menus, splitting a list in halves, or trying every move in a puzzle.

When recursion gets slow

A method that makes two recursive calls can do an enormous amount of repeated work. The naive Fibonacci, Fib(n) = Fib(n - 1) + Fib(n - 2), computes the same small values over and over, so Fib(50) would take a very long time. The cure is memoization: store each answer in a Dictionary<int, long> (or an array) the first time you compute it, and check there before recursing.

Local functions recurse too

Local functions in top-level code can call themselves just like methods in a class. Mark them static when they only use their parameters, which is exactly the situation for most recursive helpers.

Further reading

  • Methods
  • Local functions
  • StackOverflowException

Write a recursive local function static int DigitSum(long n) that returns the sum of the digits of a non-negative number. Then write a recursive static int DigitalRoot(long n): if n has one digit, it is the answer; otherwise the answer is the digital root of its digit sum.

Read one non-negative whole number (up to the size of a long) and print both values.

Sample input:

98765

Sample output:

Digit sum: 35
Digital root: 8

You have three pegs, A, B and C, and n disks stacked on A, largest at the bottom. Move them all to C, one disk at a time, never putting a bigger disk on a smaller one.

The recursive idea: to move n disks from A to C, first move n - 1 disks from A to B (using C as the spare), then move disk n from A to C, then move the n - 1 disks from B to C (using A as the spare). Moving zero disks does nothing.

Read n (0 to 10) and print every move as Move disk <d> from <from> to <to>, then Total moves: <count>. Have your function return the number of moves it made.

Sample input:

2

Sample output:

static long Factorial(int n)
{
    if (n <= 1) return 1;            // base case
    return n * Factorial(n - 1);     // recursive case
}
static int SumDigits(long n)
{
    if (n < 10) return (int)n;                   // a single digit
    return (int)(n % 10) + SumDigits(n / 10);    // last digit + the rest
}

static string Reverse(string s) =>
    s.Length == 0 ? "" : Reverse(s[1..]) + s[0];
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Total moves: 3