Recursion in C

Recursion is a technique where a function calls itself to solve a problem.

In this lesson, you will learn:

• What recursion is and how it works.
• How to implement recursive functions.
• The difference between recursion and iteration.

Recursion is when a function calls itself to solve a smaller part of a problem.

Example syntax:

void function() { function(); // Recursive call }

Every recursive function must have a base case to prevent infinite recursion.

This program demonstrates recursion by printing numbers from 5 to 1.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

A recursive function must include a base case to stop recursion.

Example:

if (n == 0) return;

Without a base case, the function will call itself infinitely, causing a stack overflow.

This program calculates the factorial of a number using recursion.

#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1);
}

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

Recursion and iteration (loops) can achieve the same results, but they work differently.

Differences:

• Recursion uses function calls and requires more memory.
• Iteration uses loops and is generally more efficient.
• Recursion makes code simpler for problems like tree traversal.

This program calculates the Fibonacci sequence using recursion.

#include <stdio.h>

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

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

Recursion is useful for problems that involve:

• Tree traversal.
• Backtracking (e.g., solving mazes).
• Mathematical problems like factorial and Fibonacci.

In this lesson, you learned:

• What recursion is and how it works.
• The importance of a base case.
• The difference between recursion and iteration.

Next, we will explore arrays and strings in C!