#Lecture 38 — Recursion & Function Design

Some problems are made of smaller copies of themselves. A function that calls itself — recursion — solves them directly. And with all the function tools now in hand, we learn what makes a function well designed.

Contents

Prerequisites · Connection · Objectives · Lesson · Code Examples · Common Mistakes · Best Practices · Mini Challenge · Practice Questions · Answers · Takeaways

Every error message in this lecture is real. Each one was produced by running the code shown on Dart 3.12.2, so you will recognize it when you meet it yourself.

#Prerequisites

Students should already understand, from Lectures 001–037:

• for and while loops (Lectures 026–028)
• parameters, return values, and early return (Lecture 031)
• arrow functions (Lecture 034)
• top-level variables that a function can change (Lectures 030 and 037)

#Connection With Previous Lectures

In Lecture 030 we saw that a function can call another function. So what happens if a function calls itself?

Think about the factorial of 5, written 5!: it is 5 × 4 × 3 × 2 × 1. Look closer and 5! is simply 5 × 4! — and 4! is 4 × 3!. The problem contains a smaller copy of itself. A loop can calculate it, but a function that calls itself can say it exactly as we just did.

Category 6 gave us many ways to write functions. Its last lecture also asks: what makes a function good?

#Learning Objectives

By the end of this lecture you will be able to:

• Explain what a recursive function is
• Identify the base case and the recursive case
• Write recursive countdown, factorial, sum-of-digits, and power functions
• Recognize a Stack Overflow error and its cause
• Choose between recursion and a loop
• Design functions with a single responsibility and a clear name
• Tell a pure function from one with side effects
• Use guard clauses to handle bad input first

#1. What Is Recursion?

A recursive function is a function that calls itself.

Analogy — think of a set of nesting dolls. You open a doll and find a smaller doll inside. You keep opening until you reach the tiniest doll, which does not open. That last doll is what makes the job finish.

void countDown(int n) {
  if (n == 0) {
    print('Liftoff!');
    return;
  }
  print(n);
  countDown(n - 1);
}

void main() {
  countDown(3);
}

3
2
1
Liftoff!

countDown(3) prints 3 and calls countDown(2), which calls countDown(1), which calls countDown(0) — the tiniest doll.

#2. Base Case and Recursive Case

Every recursive function needs two parts:

• The base case — the simplest input, answered without calling itself. Above, it is n == 0.
• The recursive case — the function calls itself with a smaller input: n - 1.

Each call moves one step closer to the base case. When it is reached, the calls stop.

#3. Factorial — Returning a Value

Recursion becomes powerful when each call returns a value:

int factorial(int n) {
  if (n <= 1) {
    return 1; // base case
  }
  return n * factorial(n - 1); // recursive case
}

void main() {
  print(factorial(5));
}

120

Dart cannot finish 5 * factorial(4) until factorial(4) returns, so the calls wait for one another, like a stack of plates:

The answers travel back up the table. This pile of waiting calls is the call stack.

#4. Sum of Digits

n % 10 gives the last digit, and n ~/ 10 removes it. That splits a number into "last digit" plus "a smaller number":

int sumOfDigits(int n) {
  if (n < 10) {
    return n;
  }
  return n % 10 + sumOfDigits(n ~/ 10);
}

void main() {
  print(sumOfDigits(472));
}

13

sumOfDigits(472) is 2 + sumOfDigits(47), which is 2 + 7 + sumOfDigits(4), which is 2 + 7 + 4.

#5. Power

base to the power exponent is base multiplied by itself exponent times. Anything to the power 0 is 1 — the base case:

int power(int base, int exponent) {
  if (exponent == 0) {
    return 1;
  }
  return base * power(base, exponent - 1);
}

void main() {
  print(power(2, 10));
}

1024

Only exponent shrinks; base is passed along unchanged.

#6. A Missing Base Case

Remove the base case, and the function never stops calling itself:

void countDown(int n) {
  print(n);
  countDown(n - 1); // ✗ no base case
}

void main() {
  // countDown(3); // ✗ crashes with Stack Overflow
}

When we ran that call, it printed 3, 2, 1, 0, -1, … down to about -19304, then crashed:

Unhandled exception:
Stack Overflow
#0      int.toString (dart:core-patch/integers.dart:619:3)
#1      countDown (file:///.../main.dart:2:3)
#2      countDown (file:///.../main.dart:3:3)
#3      countDown (file:///.../main.dart:3:3)

Every waiting call takes a little memory. The call stack has a limit, and thousands of calls filled it. Unlike the infinite loop of Lecture 028, recursion without a base case does stop — with a crash. We will learn to handle crashes in Lecture 084 — try, catch & finally.

#7. Recursion vs Loops

Anything recursion does, a loop can do too:

int factorialLoop(int n) {
  var result = 1;
  for (var i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

int factorialRecursive(int n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorialRecursive(n - 1);
}

void main() {
  print(factorialLoop(6));
  print(factorialRecursive(6));
}

720
720

• Use a loop for simple repetition, and when the number of steps may be very large — a loop never overflows the stack.
• Use recursion when the problem naturally contains smaller copies of itself and the recursive version is clearly easier to read.

#8. One Job per Function

Now, function design. A well-designed function has a single responsibility: it does one job. Compare:

void handleOrder(double price, int quantity) {
  var total = price * quantity;
  if (total >= 1000) {
    total = total * 0.9;
  }
  print('Total: $total');
}

void main() {
  handleOrder(400, 3);
}

Total: 1080.0

handleOrder calculates, applies a discount, and prints. No other code can reuse the discount rule or get the total back. Split it:

double subtotal(double price, int quantity) => price * quantity;

double applyDiscount(double amount) {
  if (amount >= 1000) {
    return amount * 0.9;
  }
  return amount;
}

void main() {
  var total = applyDiscount(subtotal(400, 3));
  print('Total: $total');
}

Total: 1080.0

Each function is small, has one job, and can be reused on its own. If describing a function needs the word "and", it probably does too much.

#9. Good Names

A function's name is how the caller understands it. Name the job:

• Actions are verbs: calculateTotal, printReceipt, applyDiscount.
• Questions that return a bool start with is, has, or can: isAdult, hasPassed.
• Avoid vague names: doStuff, process, data2.

bool hasPassed(int marks) => marks >= 50;

void main() {
  if (hasPassed(72)) {
    print('Ali passed');
  }
}

Ali passed

#10. Pure Functions and Side Effects

A pure function uses only its parameters and returns a result. Same input, same output, every time — and nothing else changes. A side effect is anything a function does besides returning a value: printing, or changing a variable outside it.

var total = 0;

void addToTotal(int amount) {
  total += amount; // side effect
}

int add(int a, int b) => a + b; // pure

void main() {
  addToTotal(5);
  addToTotal(5);
  print(total);
  print(add(5, 5));
  print(add(5, 5));
}

10
10
10

addToTotal changes total behind the caller's back; add(5, 5) is always 10. Programs need side effects (printing is one), so keep them in a few clear places and make the calculations pure.

#11. Guard Clauses

A guard clause is an early return at the top of a function that rejects bad input first. Without guards, the checks pile up in nested ifs:

String withdrawNested(int balance, int amount) {
  if (amount > 0) {
    if (amount <= balance) {
      return 'New balance: ${balance - amount}';
    } else {
      return 'Not enough money';
    }
  } else {
    return 'Invalid amount';
  }
}

String withdraw(int balance, int amount) {
  if (amount <= 0) return 'Invalid amount';
  if (amount > balance) return 'Not enough money';
  return 'New balance: ${balance - amount}';
}

void main() {
  print(withdrawNested(1000, 300));
  print(withdraw(1000, 300));
  print(withdraw(1000, 5000));
  print(withdraw(1000, -5));
}

New balance: 700
New balance: 700
Not enough money
Invalid amount

Both behave the same, but withdraw reads top to bottom: bad cases out, then the work. A recursive base case is a guard clause too — it handles the simplest input first.

#12. A Real-World Example

Sara saves money at 10% interest per year. How much will she have after a number of years?

double balanceAfter(double balance, int years) {
  if (years == 0) return balance; // base case
  return balanceAfter(balance * 1.1, years - 1);
}

String formatMoney(double amount) => amount.toStringAsFixed(2);

void printSavings(String name, double start, int years) {
  if (years < 0) {
    print('Years cannot be negative');
    return;
  }
  var end = balanceAfter(start, years);
  print('$name: ${formatMoney(start)} -> ${formatMoney(end)} in $years years');
}

void main() {
  printSavings('Sara', 1000, 3);
  printSavings('Ali', 500, 0);
  printSavings('Zayan', 200, -1);
}

Sara: 1000.00 -> 1331.00 in 3 years
Ali: 500.00 -> 500.00 in 0 years
Years cannot be negative

balanceAfter is recursive and pure. formatMoney is pure. printSavings holds the only side effect, starts with a guard clause that stops a negative year count from skipping past the base case, and every name says what its function does.

#Code Examples

#Example 1 — Counting Up

void countUp(int n) {
  if (n == 0) return;
  countUp(n - 1);
  print(n);
}

void main() {
  countUp(3);
}

1
2
3

The print comes after the recursive call, so it runs as the calls return — smallest first.

#Example 2 — Sum from 1 to n

int sumTo(int n) {
  if (n == 0) return 0;
  return n + sumTo(n - 1);
}

void main() {
  print(sumTo(100));
}

5050

#Example 3 — Factorial Table

int factorial(int n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

void main() {
  for (var i = 1; i <= 5; i++) {
    print('$i! = ${factorial(i)}');
  }
}

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

#Example 4 — Power of Three

int power(int base, int exponent) {
  if (exponent == 0) return 1;
  return base * power(base, exponent - 1);
}

void main() {
  print(power(3, 4));
}

81

#Example 5 — Counting Digits

int countDigits(int n) {
  if (n < 10) return 1;
  return 1 + countDigits(n ~/ 10);
}

void main() {
  print(countDigits(7));
  print(countDigits(2026));
}

1
4

#Example 6 — Reversing Text

String reverse(String text) {
  if (text.length <= 1) return text;
  return reverse(text.substring(1)) + text[0];
}

void main() {
  print(reverse('Dart'));
}

traD

#Example 7 — Student Marks

int total(int math, int science, int english) => math + science + english;

double average(int sum) => sum / 3;

String grade(double average) {
  if (average >= 80) return 'A';
  if (average >= 60) return 'B';
  return 'C';
}

void main() {
  var sum = total(80, 75, 85);
  var avg = average(sum);
  print('Ali: $sum, $avg, ${grade(avg)}');
}

Ali: 240, 80.0, A

#Example 8 — Shopping Total

double lineTotal(double price, int quantity) => price * quantity;

double addTax(double amount) => amount * 1.05;

void printBill(double amount) {
  print('Bill: ${amount.toStringAsFixed(2)}');
}

void main() {
  var amount = lineTotal(250, 3) + lineTotal(40, 5);
  printBill(addTax(amount));
}

Bill: 997.50

#Example 9 — Months to a Savings Target

int monthsToTarget(int balance, int target, int deposit) {
  if (balance >= target) return 0;
  return 1 + monthsToTarget(balance + deposit, target, deposit);
}

void main() {
  print('Zayan needs ${monthsToTarget(150, 1000, 200)} months');
}

Zayan needs 5 months

#Example 10 — Temperature with a Guard

double? toFahrenheit(double celsius) {
  if (celsius < -273.15) return null; // colder than possible
  return celsius * 9 / 5 + 32;
}

void main() {
  print(toFahrenheit(25));
  print(toFahrenheit(-300) ?? 'Invalid temperature');
}

77.0
Invalid temperature

#Common Beginner Mistakes

1. Forgetting the base case

int sumTo(int n) {
  return n + sumTo(n - 1); // ✗ never stops
}

void main() {
  // print(sumTo(3)); // ✗
}

Unhandled exception:
Stack Overflow

2. A base case that is never reached

factorial(-1) with the base case n == 0 skips straight past 0 and overflows. Use n <= 1, or add a guard clause for negative input.

3. Not making the input smaller

// return n * factorial(n); // ✗ same n every time

The recursive call must move towards the base case: factorial(n - 1).

4. Forgetting to return the recursive result

int factorial(int n) {
  if (n <= 1) return 1;
  n * factorial(n - 1); // ✗ result thrown away
}

Error: A non-null value must be returned since the return type 'int' doesn't allow null.
int factorial(int n) {
    ^

5. One function doing everything

A function that calculates and prints cannot be reused. Split it.

6. Hidden side effects

A calculateTotal that also changes a top-level variable surprises everyone. Return the result instead.

#Best Practices

• Write the base case first, then the recursive case.
• Make sure every recursive call moves closer to the base case.
• Prefer a loop for simple repetition or very large inputs.
• Give each function one job; if describing it needs "and", split it.
• Name actions with verbs and bool questions with is, has, or can.
• Keep calculations pure; keep printing and other side effects in a few places.
• Put guard clauses at the top to reject bad input early.

#Mini Challenge

Write a recursive function repeatText(String text, int times) that returns text joined to itself times times. Use it to print Hi three times and Dart zero times (an empty line).

Your program should print exactly:

HiHiHi

Try it yourself before opening the solution.

String repeatText(String text, int times) {
  if (times <= 0) return '';
  return text + repeatText(text, times - 1);
}

void main() {
  print(repeatText('Hi', 3));
  print(repeatText('Dart', 0));
}

HiHiHi

#Practice Questions

Work through these in order — they run from beginner to application to challenge. Every question gives you exact values, so you can compare your output with the answers.

Beginner

1. Write a recursive countDown that prints 5 down to 1, then Go!.

2. Write a recursive int sumTo(int n) and print sumTo(10).

3. In this function, which line is the base case and which is the recursive case? What does mystery(4) print?

   dartCopy

   int mystery(int n) {
     if (n == 0) return 0;
     return 2 + mystery(n - 1);
   }

Application

4. Write a recursive power and print power(5, 3).

5. Write a recursive int productOfDigits(int n) and print productOfDigits(234).

6. Write a recursive int multiply(int a, int b) that uses only addition (a added b times). Print multiply(6, 7).

7. Is this function pure? Rewrite it as a pure function int addPoints(int score, int points) and print addPoints(40, 25).

   dartCopy

   var score = 0;
   void addPoints(int points) {
     score += points;
   }

8. Split this into a pure double finalPrice(double price) and a main that prints:

   dartCopy

   void shop(double price) {
     var finalPrice = price - price * 0.2;
     print('Final price: $finalPrice');
   }

   Use price = 1500.

Challenge

9. Rewrite with guard clauses, without changing behavior, then print ticketPrice(5), ticketPrice(30), and ticketPrice(-2):

   dartCopy

   String ticketPrice(int age) {
     if (age >= 0) {
       if (age < 12) {
         return 'Child: 200';
       } else {
         return 'Adult: 500';
       }
     } else {
       return 'Invalid age';
     }
   }

10. The Fibonacci numbers start 1, 1, and each next number is the sum of the two before it. Write a recursive int fibonacci(int n) (with fibonacci(1) and fibonacci(2) both 1) and print the first 10 on one line, separated by spaces.

#Practice Answers

#Question 1 — Solution

void countDown(int n) {
  if (n == 0) {
    print('Go!');
    return;
  }
  print(n);
  countDown(n - 1);
}

void main() {
  countDown(5);
}

5
4
3
2
1
Go!

#Question 2 — Solution

int sumTo(int n) {
  if (n == 0) return 0;
  return n + sumTo(n - 1);
}

void main() {
  print(sumTo(10));
}

55

#Question 3 — Solution

if (n == 0) return 0; is the base case; return 2 + mystery(n - 1); is the recursive case. Each call adds 2, so mystery(n) is 2 * n.

int mystery(int n) {
  if (n == 0) return 0;
  return 2 + mystery(n - 1);
}

void main() {
  print(mystery(4));
}

8

#Question 4 — Solution

int power(int base, int exponent) {
  if (exponent == 0) return 1;
  return base * power(base, exponent - 1);
}

void main() {
  print(power(5, 3));
}

125

#Question 5 — Solution

int productOfDigits(int n) {
  if (n < 10) return n;
  return n % 10 * productOfDigits(n ~/ 10);
}

void main() {
  print(productOfDigits(234));
}

24

#Question 6 — Solution

int multiply(int a, int b) {
  if (b == 0) return 0;
  return a + multiply(a, b - 1);
}

void main() {
  print(multiply(6, 7));
}

42

#Question 7 — Solution

It is not pure: it changes the top-level score and returns nothing.

int addPoints(int score, int points) => score + points;

void main() {
  print(addPoints(40, 25));
}

65

#Question 8 — Solution

double finalPrice(double price) => price - price * 0.2;

void main() {
  print('Final price: ${finalPrice(1500)}');
}

Final price: 1200.0

#Question 9 — Solution

String ticketPrice(int age) {
  if (age < 0) return 'Invalid age';
  if (age < 12) return 'Child: 200';
  return 'Adult: 500';
}

void main() {
  print(ticketPrice(5));
  print(ticketPrice(30));
  print(ticketPrice(-2));
}

Child: 200
Adult: 500
Invalid age

#Question 10 — Solution

int fibonacci(int n) {
  if (n <= 2) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

void main() {
  var line = '';
  for (var i = 1; i <= 10; i++) {
    line += '${fibonacci(i)} ';
  }
  print(line.trim());
}

1 1 2 3 5 8 13 21 34 55

Each call makes two more calls, so for large n a loop is much faster.

#Quick Revision

1. What is a recursive function?
2. What are the base case and the recursive case?
3. What happens when a recursive function has no base case?
4. Why must each recursive call use a smaller input?
5. When is a loop a better choice than recursion?
6. What does "single responsibility" mean for a function?
7. What makes a function pure?
8. What is a guard clause?

#Key Takeaways

• A recursive function calls itself to solve a smaller copy of the same problem.
• The base case answers without recursion; the recursive case calls itself with a smaller input.
• Waiting calls pile up on the call stack; too many cause a Stack Overflow crash.
• Every problem solved with recursion can also be solved with a loop — prefer loops for simple repetition and very large inputs.
• Give each function one job, keep it small, and name it after that job.
• Pure functions depend only on their parameters and change nothing else.
• Keep side effects, such as printing, in a few clear places.
• Guard clauses reject bad input at the top, keeping the main path flat.

#What's Next?

Lecture 039 — Introduction to Lists. Category 6 is complete: you can write, combine, and design functions. But so far every function has worked with a few separate values — three marks, one price. Real programs handle a whole class of students or a full shopping cart. Next we start Category 7 and learn to store many values together in a List.