C#, lesson 11
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.
Every recursive method needs:
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.
624Each 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:
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.
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 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.
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:
98765Sample output:
Digit sum: 35
Digital root: 8You 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:
2Sample 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