Skip to main content

​
Introduction to Recursion

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar sub-problems. Each recursive call works on a simpler version of the original problem until reaching a base case that can be solved directly.
Every recursive function must have:
  1. A base case - the stopping condition
  2. A recursive case - the function calling itself with modified parameters
  3. Progress toward the base case

​
Basic Recursion Example

Here’s a simple example that prints a string using recursion: 
#include "main.h"

/**
 * _puts_recursion - print a string
 * @str: string to print
 * Return: void
 */
void _puts_recursion(char *str)
{
    if (*str == '\0')
    {
        _putchar('\n');
        return;
    }
    _putchar(*str);
    _puts_recursion(str + 1);
}
How it works:
  • Base case: When we reach the null terminator ('\0'), print a newline and return
  • Recursive case: Print the current character, then call the function with the next character
  • Progress: Each call moves one character forward in the string

​
Mathematical Recursion

​
Factorial Calculation

Factorial is a classic example of recursion. The factorial of n (n!) is the product of all positive integers less than or equal to n. 
#include "main.h"

/**
 * factorial - factorial of a given number
 * @n: number
 * Return: -1 if n is less than 0, 1 if n is 0, or n!
*/
int factorial(int n)
{
    if (n < 0)
        return (-1);
    if (n == 0)
        return (1);
    return (n * factorial(n - 1));
}
Example execution for factorial(5): 
factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1 (base case)

Result: 5 * 4 * 3 * 2 * 1 * 1 = 120

​
Power Function

Calculating powers using recursion demonstrates how to handle multiple conditions: 
/**
 * _pow_recursion - returns the value of x raised to the power of y
 * @x: base number
 * @y: exponent
 * Return: -1 if y is less than 0, or x^y
 */
int _pow_recursion(int x, int y)
{
    if (y < 0)
        return (-1);
    if (y == 0)
        return (1);
    return (x * _pow_recursion(x, y - 1));
}

​
Advanced Recursion with Helper Functions

​
Square Root Calculation

Some recursive problems require a helper function to maintain additional state: 
#include "main.h"

/**
 * _sqrt_recursion - returns the natural square root of a number
 * @n: number
 * Return: -1 if n doesn't have a natural square root
 * or the natural square root of n
 */
int _sqrt_recursion(int n)
{
    return (squarerootofnumber(n, 1));
}

/**
 * squarerootofnumber - returns the natural square root of a number
 * @num: number
 * @sqroot: square root of number
 * Return: square root
 */
int squarerootofnumber(int num, int sqroot)
{
    if (sqroot * sqroot == num)
        return (sqroot);
    else if (sqroot * sqroot > num)
        return (-1);
    else
        return (squarerootofnumber(num, sqroot + 1));
}
Why use a helper function?
  • The main function has a clean interface (_sqrt_recursion(n))
  • The helper function manages the iteration variable (sqroot)
  • This pattern is common when you need to track additional state

​
Prime Number Detection

Another example using a helper function to check divisibility: 
#include "main.h"

/**
 * is_prime_number - find if integer is a prime number
 * @n: integer
 * Return: 1 if input is prime, 0 otherwise
 */
int is_prime_number(int n)
{
    return (prime(n, 2));
}

/**
 * prime - find if integer is a prime number
 * @n: integer
 * @res: integer
 * Return: 1 if input is prime, 0 otherwise
 */
int prime(int n, int res)
{
    if (res >= n && n > 1)
        return (1);
    else if (n % res == 0 || n <= 1)
        return (0);
    else
        return (prime(n, res + 1));
}

​
Recursion vs Iteration

Advantages

  • Clean, elegant code for naturally recursive problems
  • Easier to understand for tree/graph operations
  • Matches mathematical definitions

Disadvantages

  • Uses more memory (call stack)
  • Can be slower than iteration
  • Risk of stack overflow with deep recursion

​
Common Recursive Patterns

​
Linear Recursion

The function makes a single recursive call: 
int strlen_recursion(char *s)
{
    if (*s == '\0')
        return (0);
    return (1 + strlen_recursion(s + 1));
}

​
Tail Recursion

The recursive call is the last operation in the function: 
void print_rev_recursion(char *s)
{
    if (*s == '\0')
        return;
    print_rev_recursion(s + 1);
    _putchar(*s);
}
Tail-recursive functions can sometimes be optimized by the compiler into loops, but this isn’t guaranteed in C without specific compiler flags.

​
Best Practices

  1. Always define a clear base case
    • Without it, your function will recurse infinitely
    • Test edge cases (0, negative numbers, empty strings)
  2. Ensure progress toward the base case
    • Each recursive call should move closer to the base case
    • Otherwise, you’ll have infinite recursion
  3. Consider the call stack depth
    • Deep recursion can cause stack overflow
    • For large inputs, iteration might be better
  4. Use helper functions when needed
    • Keep the public API simple
    • Use helpers to manage additional parameters
When debugging recursive functions, add print statements to track:
  • The input parameters at each level
  • The depth of recursion
  • The return values at each level

​
Practice Problems

The 0x08-recursion directory includes implementations of:
  • _puts_recursion() - Print a string recursively
  • _print_rev_recursion() - Print a string in reverse
  • _strlen_recursion() - Calculate string length
  • factorial() - Calculate factorial
  • _pow_recursion() - Calculate power
  • _sqrt_recursion() - Find square root
  • is_prime_number() - Check if number is prime

​
Key Takeaways

  • Recursion solves problems by breaking them into smaller instances
  • Every recursive function needs a base case and recursive case
  • Helper functions are useful for managing additional state
  • Consider memory usage and stack depth for large inputs
  • Some problems are naturally recursive (trees, graphs, mathematical sequences)

Function Pointers

Learn about passing functions as arguments

Variadic Functions

Master functions with variable arguments

Build docs developers (and LLMs) love

Get started for freeTalk to us