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.
Was this tutorial helpful ?