Dart Recursion
Functions that call themselves to solve problems step by step
🔄 What is Recursion?
Recursion in Dart is when a function calls itself to solve a problem by breaking it into smaller, similar subproblems. It's like solving a puzzle by solving smaller versions of the same puzzle.
// Simple recursive function to calculate factorial
int factorial(int n) {
// Base case: stop the recursion
if (n <= 1) {
return 1;
}
// Recursive case: function calls itself
return n * factorial(n - 1);
}
print(factorial(5)); // 5 * 4 * 3 * 2 * 1 = 120
Output:
120
Recursion Components
Base Case
Condition that stops recursion
if (n <= 0) {
return 1; // Stop here!
}Recursive Case
Function calls itself with modified input
return n * factorial(n - 1);
// Calls itself with smaller nProblem Reduction
Each call works on smaller problem
factorial(5) → factorial(4) → factorial(3)
→ factorial(2) → factorial(1)Call Stack
Functions stack up until base case
factorial(1) returns 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6🔹 Basic Recursive Functions
Understanding recursion with simple examples:
// Countdown function
void countdown(int n) {
// Base case
if (n <= 0) {
print('Blast off! 🚀');
return;
}
// Print current number
print(n);
// Recursive case
countdown(n - 1);
}
// Sum of numbers from 1 to n
int sumToN(int n) {
if (n <= 0) {
return 0;
}
return n + sumToN(n - 1);
}
// Power function (x^n)
double power(double x, int n) {
if (n == 0) {
return 1;
}
if (n < 0) {
return 1 / power(x, -n);
}
return x * power(x, n - 1);
}
void main() {
print('=== Countdown ===');
countdown(5);
print('\n=== Sum Examples ===');
print('Sum 1 to 5: ${sumToN(5)}');
print('Sum 1 to 10: ${sumToN(10)}');
print('\n=== Power Examples ===');
print('2^3 = ${power(2, 3)}');
print('5^0 = ${power(5, 0)}');
print('2^-2 = ${power(2, -2)}');
}Output:
=== Countdown ===
5
4
3
2
1
Blast off! 🚀
=== Sum Examples ===
Sum 1 to 5: 15
Sum 1 to 10: 55
=== Power Examples ===
2^3 = 8.0
5^0 = 1.0
2^-2 = 0.25
🔹 Fibonacci Sequence
Classic recursion example - each number is sum of previous two:
// Fibonacci using recursion
int fibonacci(int n) {
// Base cases
if (n <= 0) return 0;
if (n == 1) return 1;
// Recursive case: F(n) = F(n-1) + F(n-2)
return fibonacci(n - 1) + fibonacci(n - 2);
}
// More efficient version with memoization
Map _fibCache = {};
int fibonacciOptimized(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
// Check if already calculated
if (_fibCache.containsKey(n)) {
return _fibCache[n]!;
}
// Calculate and store result
_fibCache[n] = fibonacciOptimized(n - 1) + fibonacciOptimized(n - 2);
return _fibCache[n]!;
}
void main() {
print('=== Fibonacci Sequence ===');
print('First 10 Fibonacci numbers:');
for (int i = 0; i < 10; i++) {
print('F($i) = ${fibonacci(i)}');
}
print('\n=== Optimized Version ===');
print('F(20) = ${fibonacciOptimized(20)}');
print('F(30) = ${fibonacciOptimized(30)}');
} Output:
=== Fibonacci Sequence ===
First 10 Fibonacci numbers:
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
=== Optimized Version ===
F(20) = 6765
F(30) = 832040
🔹 Working with Lists
Recursive functions for list operations:
// Find maximum element in list
int findMax(List list, [int index = 0]) {
// Base case: only one element left
if (index == list.length - 1) {
return list[index];
}
// Recursive case: compare current with max of rest
int maxOfRest = findMax(list, index + 1);
return list[index] > maxOfRest ? list[index] : maxOfRest;
}
// Reverse a string recursively
String reverseString(String str) {
// Base case: empty or single character
if (str.length <= 1) {
return str;
}
// Recursive case: last char + reverse of rest
return str[str.length - 1] + reverseString(str.substring(0, str.length - 1));
}
// Check if string is palindrome
bool isPalindrome(String str, [int start = 0, int? end]) {
end ??= str.length - 1;
// Base case: reached middle
if (start >= end) {
return true;
}
// Check if characters match and recurse
if (str[start] != str[end]) {
return false;
}
return isPalindrome(str, start + 1, end - 1);
}
void main() {
var numbers = [3, 7, 2, 9, 1, 8, 4];
print('Numbers: $numbers');
print('Maximum: ${findMax(numbers)}');
print('\n=== String Operations ===');
var text = 'hello';
print('Original: $text');
print('Reversed: ${reverseString(text)}');
print('\n=== Palindrome Check ===');
var words = ['racecar', 'hello', 'madam', 'world'];
for (var word in words) {
print('$word is palindrome: ${isPalindrome(word)}');
}
} Output:
Numbers: [3, 7, 2, 9, 1, 8, 4]
Maximum: 9
=== String Operations ===
Original: hello
Reversed: olleh
=== Palindrome Check ===
racecar is palindrome: true
hello is palindrome: false
madam is palindrome: true
world is palindrome: false
🔹 Tree Traversal Example
Recursion is perfect for tree-like structures:
// Simple binary tree node
class TreeNode {
int value;
TreeNode? left;
TreeNode? right;
TreeNode(this.value, [this.left, this.right]);
}
// Recursive tree operations
class TreeOperations {
// Calculate tree height
static int height(TreeNode? node) {
if (node == null) return 0;
int leftHeight = height(node.left);
int rightHeight = height(node.right);
return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}
// Count total nodes
static int countNodes(TreeNode? node) {
if (node == null) return 0;
return 1 + countNodes(node.left) + countNodes(node.right);
}
// In-order traversal (left, root, right)
static void inOrder(TreeNode? node, List result) {
if (node == null) return;
inOrder(node.left, result); // Visit left subtree
result.add(node.value); // Visit root
inOrder(node.right, result); // Visit right subtree
}
}
void main() {
// Create a simple binary tree
// 1
// / \
// 2 3
// / \
// 4 5
var root = TreeNode(1,
TreeNode(2, TreeNode(4), TreeNode(5)),
TreeNode(3)
);
print('Tree height: ${TreeOperations.height(root)}');
print('Total nodes: ${TreeOperations.countNodes(root)}');
var traversal = [];
TreeOperations.inOrder(root, traversal);
print('In-order traversal: $traversal');
} Output:
Tree height: 3
Total nodes: 5
In-order traversal: [4, 2, 5, 1, 3]