Recursion Deep Dive
Recursion Basics
A recursive function solves a problem by calling itself on a smaller version of the same problem, relying on the language's call stack to keep track of all the in-progress calls. It's a different way of expressing repetition than a loop, often matching the natural structure of the problem itself (like trees or nested data).
Example: Recursion Basics
#include <iostream>
using namespace std;
int countDown(int n) {
if (n <= 0) return 0;
cout << n << " ";
return countDown(n - 1);
}
int main() {
countDown(5);
return 0;
}public class Main {
static void countDown(int n) {
if (n <= 0) return;
System.out.print(n + " ");
countDown(n - 1);
}
public static void main(String[] args) {
countDown(5);
}
}def count_down(n):
if n <= 0:
return
print(n, end=" ")
count_down(n - 1)
count_down(5)#include <stdio.h>
void countDown(int n) {
if (n <= 0) return;
printf("%d ", n);
countDown(n - 1);
}
int main() {
countDown(5);
return 0;
}Login to try C/C++/Java code in the editor
Base Case
Every recursive function needs a base case that returns a value directly without making another recursive call, or the calls would never stop and the program would crash with a stack overflow. Getting the base case right is usually the hardest and most important part of writing correct recursion.
Example: Base Case
#include <iostream>
using namespace std;
int sumTo(int n) {
if (n == 0) return 0;
return n + sumTo(n - 1);
}
int main() {
cout << sumTo(4);
return 0;
}public class Main {
static int sumTo(int n) {
if (n == 0) return 0;
return n + sumTo(n - 1);
}
public static void main(String[] args) {
System.out.println(sumTo(4));
}
}def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
print(sum_to(4))#include <stdio.h>
int sumTo(int n) {
if (n == 0) return 0;
return n + sumTo(n - 1);
}
int main() {
printf("%d", sumTo(4));
return 0;
}Login to try C/C++/Java code in the editor
Recursive Flow
When a function calls itself, that call is pushed onto the call stack and the current call pauses until the new one returns a result. Execution unwinds back through each paused call in reverse order, which is why recursive traces often show work happening 'on the way back up.'
Example: Recursive Flow
#include <iostream>
using namespace std;
void trace(int n) {
if (n == 0) { cout << "reached base" << endl; return; }
cout << "entering " << n << endl;
trace(n - 1);
cout << "leaving " << n << endl;
}
int main() {
trace(3);
return 0;
}public class Main {
static void trace(int n) {
if (n == 0) { System.out.println("reached base"); return; }
System.out.println("entering " + n);
trace(n - 1);
System.out.println("leaving " + n);
}
public static void main(String[] args) {
trace(3);
}
}def trace(n):
if n == 0:
print("reached base")
return
print("entering", n)
trace(n - 1)
print("leaving", n)
trace(3)#include <stdio.h>
void trace(int n) {
if (n == 0) { printf("reached base\n"); return; }
printf("entering %d\n", n);
trace(n - 1);
printf("leaving %d\n", n);
}
int main() {
trace(3);
return 0;
}Login to try C/C++/Java code in the editor
Recursive Arrays
Recursion is a natural fit for processing arrays or lists element by element: handle the first element, then recursively handle the rest of the list as a smaller version of the same problem. This mirrors how many list operations are defined mathematically.
Example: Recursive Arrays
#include <iostream>
using namespace std;
int sumArray(int arr[], int n) {
if (n == 0) return 0;
return arr[0] + sumArray(arr + 1, n - 1);
}
int main() {
int arr[] = {1, 2, 3, 4};
cout << sumArray(arr, 4);
return 0;
}public class Main {
static int sumArray(int[] arr, int i) {
if (i == arr.length) return 0;
return arr[i] + sumArray(arr, i + 1);
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
System.out.println(sumArray(arr, 0));
}
}def sum_array(arr):
if not arr:
return 0
return arr[0] + sum_array(arr[1:])
print(sum_array([1, 2, 3, 4]))#include <stdio.h>
int sumArray(int arr[], int n) {
if (n == 0) return 0;
return arr[0] + sumArray(arr + 1, n - 1);
}
int main() {
int arr[] = {1, 2, 3, 4};
printf("%d", sumArray(arr, 4));
return 0;
}Login to try C/C++/Java code in the editor
Recursion Practice
A strong recursive solution should make clear progress toward the base case with every call — usually by shrinking the input by at least one element or halving it. If you can't articulate what specifically gets smaller each call, the recursion likely won't terminate correctly.
Example: Recursion Practice
#include <iostream>
using namespace std;
int countDigits(int n) {
if (n < 10) return 1;
return 1 + countDigits(n / 10);
}
int main() {
cout << countDigits(4521);
return 0;
}public class Main {
static int countDigits(int n) {
if (n < 10) return 1;
return 1 + countDigits(n / 10);
}
public static void main(String[] args) {
System.out.println(countDigits(4521));
}
}def count_digits(n):
if n < 10:
return 1
return 1 + count_digits(n // 10)
print(count_digits(4521))#include <stdio.h>
int countDigits(int n) {
if (n < 10) return 1;
return 1 + countDigits(n / 10);
}
int main() {
printf("%d", countDigits(4521));
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 7 topics to unlock
0/7 topics done
Complete these topics first: