Recursion in C

Introduction

A function calling itself or calling a function within the same function is called recursion in C. The calling of a function to itself proceeds until it reaches the ‘base condition’. Recursion can be used to solve big problems like finding the sum of the 1st ten natural numbers.

Example

#include<stdio.h>

int sum (int a)

{

            int s;

            if (a==1)

            {

                        return a;// base condition

            }

            else

            {

            s=a+ sum(a-1);

            }

            return s;

}

int main()

{

            int k;

            k=sum(10);

            printf("sum of 1st 10 natural numbers:\n %d",k);

            return 0;

}

Output

Recursion in C

Explanation

int sum (int a) A function named ‘sum’ of ‘int’ datatype is declared to have an ‘int’ type variable passed as an argument. Now, in its definition ‘if’ condition will return 1 if ‘a’ is 1. Otherwise, the else part is executed.

s=a+ sum(a-1) This statement is calling the ‘sum’ function with ‘a-1’ passed as argument.

The ‘main ( )’ function calls the ‘sum’ function by passing 10 as an argument. Since the value of ‘a’ is 10, the function definition ‘else’ part will be executed.

‘s=10+sum (10-1)’ will be the result by passing ‘a=10’. Now, the sum function is calling itself with ‘a=9’. And this procedure goes on until ‘a’ becomes 1.

s=10+sum (9)

s=10+(9+sum (8))

s=10+9+(8+sum (7))

s=10+9+8+(7+sum (6))

s=10+9+8+7+(6+sum (5))

s=10+9+8+7+6+(5+sum (4))

s=10+9+8+7+6+5+(4+sum (3))

s=10+9+8+7+6+5+4+(3+sum (2))

s=10+9+8+7+6+5+4+3+(2+sum (1))

s=54+sum (1)

Now, the value of ‘a’ is 1, which means it has reached the base condition. The ‘if’ condition will become true, and it returns ‘a’ only, i.e.1. So, we get,

s=54+1

s=55, the value which is obtained on the output screen. In this way, this long process is solved very easily using ‘recursion’.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.