Recursive Functions in Dart

What is Recursion?

A recursive function is a function that calls itself to solve a smaller version of the same problem. Each recursive call moves closer to a base case that stops the recursion.

Base Case

Every recursive function must have a base case — a condition that stops the recursion. Without it, the function calls itself infinitely until a stack overflow error occurs.

Examples

// Factorial: n! = n × (n-1) × ... × 1
int factorial(int n) {
  if (n <= 1) return 1;       // base case
  return n * factorial(n - 1); // recursive call
}

// Fibonacci: F(n) = F(n-1) + F(n-2)
int fibonacci(int n) {
  if (n <= 1) return n;        // base case
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// Sum of digits
int digitSum(int n) {
  if (n < 10) return n;        // base case
  return n % 10 + digitSum(n ~/ 10);
}

void main() {
  print(factorial(5));   // 120
  print(factorial(10));  // 3628800

  for (int i = 0; i < 8; i++) {
    print('fib($i) = $${fibonacci(i)}');
  }

  print(digitSum(12345)); // 15 (1+2+3+4+5)
}

120
3628800
fib(0) = 0  fib(1) = 1  fib(2) = 1  fib(3) = 2
fib(4) = 3  fib(5) = 5  fib(6) = 8  fib(7) = 13
15

⚠️ Common Mistakes

• Missing base case: causes infinite recursion and a stack overflow.
• Wrong base case: factorial(0) should return 1, not 0.
• Exponential recursion: naive Fibonacci is O(2^n) — use memoization or iteration for large n.

🧠 Quiz

Summary

Recursive functions call themselves with a smaller input until they reach a base case. Every recursive function needs a base case to prevent infinite recursion. Common uses: factorial, Fibonacci, tree traversal, and divide-and-conquer algorithms.