C Recursion

C Flow Control?

In this tutorial, you will learn about if statement (including if...else and nested if..else) in C programming with the help of examples.

C Functions?

In this tutorial, you will be introduced to functions (both user-defined and standard library functions) in C programming. Also, you will learn why functions are used in programming.

C Programming Arrays?

In this tutorial, you will learn to work with arrays. You will learn to declare, initialize and access elements of an array with the help of examples.

C Programming Pointers?

In this tutorial, you'll learn about pointers; what pointers are, how do you use them and the common mistakes you might face when working with them with the help of examples.

C Programming Strings?

In this tutorial, you'll learn about strings in C programming. You'll learn to declare them, initialize them and use them for various I/O operations with the help of examples.

Structure And Union?

In this tutorial, you'll learn about struct types in C Programming. You will learn to define and use structures with the help of examples.

C Programming Files?

In this tutorial, you will learn about file handling in C. You will learn to handle standard I/O in C using fprintf(), fscanf(), fread(), fwrite(), fseek() etc. with the help of examples.

Additional Topics?

In this tutorial, you will learn about enum (enumeration) in C programming with the help of examples.
C Recursion

In this tutorial, you will learn to write recursive functions in C programming with the help of an example.

 

A function that calls itself is known as a recursive function. And, this technique is known as recursion.


How recursion works?

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}
How recursion works in C programming?

 

 
 

The recursion continues until some condition is met to prevent it.

To prevent infinite recursion, if…else statement (or similar approach) can be used where one branch makes the recursive call, and other doesn’t.


Example: Sum of Natural Numbers Using Recursion

#include <stdio.h>
int sum(int n);

int main() {
    int number, result;

    printf("Enter a positive integer: ");
    scanf("%d", &number);

    result = sum(number);

    printf("sum = %d", result);
    return 0;
}

int sum(int n) {
    if (n != 0)
        // sum() function calls itself
        return n + sum(n-1); 
    else
        return n;
}

Output

Enter a positive integer:3
sum = 6

Initially, the sum() is called from the main() function with number passed as an argument.

Suppose, the value of n inside sum() is 3 initially. During the next function call, 2 is passed to the sum() function. This process continues until n is equal to 0.

When n is equal to 0, the if condition fails and the else part is executed returning the sum of integers ultimately to the main() function.

Calculation of sum of natural number using recursion

Advantages and Disadvantages of Recursion

Recursion makes program elegant. However, if performance is vital, use loops instead as recursion is usually much slower.

That being said, recursion is an important concept. It is frequently used in data structure and algorithms. For example, it is common to use recursion in problems such as tree traversal.

Previous Tutorial:
C Function Types
Next Tutorial:
C Storage Class