<style> .reveal-up, .reveal-left, .reveal-right, .reveal-stagger > * { opacity: 1 !important; transform: none !important; } </style>
  1. Learn
  2. C#
  3. Arrays and methods
All lessons in this course

Getting started

Control flow

Arrays and methods

Object-oriented programming

Working with data

Functional C# and LINQ

Advanced C#

Master level

Lesson 15 of 60 14 minBeginner

Recursion

A method that calls itself: base cases, recursive cases, how the call stack handles it, and when to use a loop instead.

Recursion means a method calls itself to solve a smaller version of the same problem. It sounds strange at first, but many problems are naturally defined this way: folders contain folders, a tree’s branches have branches, and a structure’s assembly contains sub-assemblies.

The two parts of every recursive method

  1. Base case: a simple input answered directly, without calling itself. This is what stops the recursion.
  2. Recursive case: the method calls itself with a smaller input that moves toward the base case.

Factorial is the classic example: 5! = 5 × 4 × 3 × 2 × 1, which is the same as 5 × 4!. So n! = n × (n-1)!, and 1! = 1 is the base case.

Interactive

Calls go down, answers come back up

Factorial of
Factorial.cs
static int Factorial(int n){    if (n <= 1)        return 1;                 // base case: stop here    return n * Factorial(n - 1);  // recursive case} Console.WriteLine(Factorial(4));
Factorial(4) running…
Step 1 / 8
Factorial(4): is 4 <= 1? No. So it needs 4 × Factorial(3) and calls itself. This call waits.

Notice the two phases. On the way down, each call waits for the next. When the base case returns, the answers travel back up, and each waiting call finishes its multiplication. Every waiting call is a frame on the call stack.

More examples

SumDigits.cs
// Sum of digits: 4096 → 4 + 0 + 9 + 6 = 19static int SumDigits(int n){    if (n < 10) return n;                // base case: one digit    return n % 10 + SumDigits(n / 10);   // last digit + sum of the rest} Console.WriteLine(SumDigits(4096));
Output
19
Power.cs
// x to the power of n, halving n each time (fast!)static double Power(double x, int n){    if (n == 0) return 1;    double half = Power(x, n / 2);    return n % 2 == 0 ? half * half : half * half * x;} Console.WriteLine(Power(2, 10));
Output
1024

When recursion goes wrong

Broken.cs
static int Broken(int n){    return n * Broken(n - 1);   // no base case!}// Broken(5) → Broken(4) → … → Broken(-10000) → …// Process terminated: Stack overflow.

Beware of repeated work

Fibonacci.cs
// Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13 …static long FibSlow(int n) => n < 2 ? n : FibSlow(n - 1) + FibSlow(n - 2); static long FibFast(int n){    long a = 0, b = 1;    for (int i = 0; i < n; i++)    {        (a, b) = (b, a + b);    }    return a;} Console.WriteLine(FibFast(50));   // instant// FibSlow(50) makes billions of calls: it takes minutes.
Output
12586269025

FibSlow calls itself twice per level, so it recomputes the same values again and again. The loop version computes each value once. Later, in the DSA course, you will learn memoization, which fixes this while keeping the recursive style.

Recursion or a loop?

Use recursion when…Use a loop when…
The data is a tree or nested structure (folders, menus, assemblies, JSON)You simply repeat steps over a range or list
The problem splits into smaller copies of itself (divide and conquer, sorting)The depth could be very large
The recursive version is much clearerPerformance matters and the loop is just as clear
FolderSize.cs
// A natural fit: total size of a folder and all its sub-foldersstatic long FolderSize(DirectoryInfo dir){    long size = 0;    foreach (FileInfo f in dir.GetFiles())        size += f.Length;    foreach (DirectoryInfo sub in dir.GetDirectories())        size += FolderSize(sub);        // the same problem, one level down    return size;}
Quick check

What stops a recursive method from calling itself forever?

Quick check

What does SumDigits(305) return with the method above?

Practice

Write a recursive method static string Reverse(string s) that returns the string reversed (e.g. "steel" → "leets").

Show a hint

Base case: a string of length 0 or 1 is its own reverse. Recursive case: the last character + Reverse(everything except the last character).

Show the solution
Solution.cs
static string Reverse(string s){    if (s.Length <= 1) return s;    return s[^1] + Reverse(s[..^1]);   // last char + reverse of the rest} Console.WriteLine(Reverse("steel"));
Output
leets

Remember

  • A recursive method calls itself on a smaller input.
  • Always have a base case, and make every call move toward it.
  • Each pending call is a stack frame; too deep means StackOverflowException.
  • Prefer recursion for nested/tree data; prefer loops for simple repetition.
0 of 60 lessons completed