C Recursive Function

Summary: in this tutorial, you will learn about C recursive functions and how to use them effectively.

Introduction to the C recurisve function

A recursive function is a function that calls to itself until it doesn’t. For example:

void fn()
{
    // ...
     fn();
    //..
}
Code language: JavaScript (javascript)

In this example, the fn() function is a recursive function because the fn() function has a call to itself inside its function body.

Typically, a recursive function has a condition to stop calling itself. Otherwise, the recursive function will call itself indefinitely until the operating system terminates it.

Therefore, a recursive function will look like the following:

void fn()
{
    // ...
    if (expression)
        fn();
    //..
}
Code language: JavaScript (javascript)

A very simple C recursive function example

Suppose you want to develop a program that counts down from 3 to 1:

3 2 1 

The count_down() function prototype will look like this:

void count_down(int n);
Code language: JavaScript (javascript)

The following shows how to call the count_down() function:

count_down(3);

The count_down(3) should display number 3 to the output:

void count_down(int n)
{
    printf("%d ", n);

}
Code language: JavaScript (javascript)

Since the count_down() function is recursive, it needs to have a call to itself. After displaying 3, the function should display 2 and 1.

To display 2, you can call the count_down() function and pass n - 1 to the count_down() function:

void count_down(int n)
{
    // display n, and subtract 1 from it
    printf("%d ", n--);
    // show n-1
    count_down(n);
}
Code language: JavaScript (javascript)

If you call the count_down() function, it’ll call itself indenfinitely that cause the program crashed.

The count_down() function should stop calling itself once n is zero. Therefore, you need to add an if statement to the count_down() function:

void count_down(int n)
{
    // display n, and subtract 1 from it
    printf("%d ", n--);
    
    // show n-1
    if (n > 0)
        count_down(n);
}
Code language: JavaScript (javascript)

Now, you have a complete recursive function.

The following program uses the count_down() recursive function:

#include <stdio.h>

void count_down(int n);

int main()
{
    count_down(3);

    return 0;
}

// count down from n
void count_down(int n)
{
    // display n, and subtract 1 from it
    printf("%d ", n--);
    // show n-1
    if (n > 0)
        count_down(n);
}
Code language: PHP (php)

Using a recursive function to calculate the sum of the first n natural numbers

The sum of the first n natural numbers can be defined as follows:

sum(n)   = n + sum(n-1)
sum(n-1) = (n - 1) + sum(n-2)
...
sum(2)   = 1 + sum(1)
sum(1)   = 1

The following program illustrates how to calculuate the sum of the first n natural numbers:

#include <stdio.h>

int sum(int n);

int main()
{
    int n;
    // prompt for n
    printf("Enter n:");
    scanf("%d", &n);

    // calculate the sum of n
    int result = sum(n);

    // show the result
    printf("%d", result);

    return 0;
}

int sum(int n)
{
    if (n <= 0)
        return n;
    return n + sum(n - 1);
}
Code language: PHP (php)

Why recursive functions

Recursive functions allow you to break down a complex problem into identical sub-problems recursively until the sub-problems are simple enough to solve directly.

The solutions are then combined to produce the total solution to the original problem. This is a famous programming technique known as divide and conquer.

Many algorithms use the recursion technique, such as the quicksort algorithm and binary search algorithm.

Summary

• A recurisve function is a function that calls itself until it doesn’t.
• A recursive function divides a complex problem into smaller ones until they’re simple enough to solve easily.