What Are The Concepts Of Recursion In C, Definition, Types

Recursion is one of the most critical processes in C programming. It plays a vital role in the programming world. In this process, the function calls itself directly or indirectly. It is a powerful technique that can be used to solve many problems. But beginners may find it difficult sometimes.

This article will teach us more about Recursion in C and how it works. Read the complete article to learn more.

Table of Contents

What is Recursion in C?

Recursion in C is the process of solving a problem using repeated function calls until a particular condition is met directly or indirectly. Recursive functions call themselves at repeated intervals to solve a problem until a base condition is met. These function calls are also known as Recursive calls. To use recursion, we need to know two most important things.

We need to define a base case that will be used to terminate the recursion function when the boundary conditions occur.
Now, we need to define the recursive step that will be used to break the problem into subproblems. These sub-problems will be used in recursive function calls.

Recursion is often considered difficult because it is sometimes hard to define the base and boundary conditions accurately. However, recursion in C helps reduce a complex problem into a subproblem. There are many problems that use recursion to solve complex problems optimally and easily.

Recursive Function In C

It helps to break down a complex problem into smaller sub-problems. There are two most important steps while designing a recursive function. The base condition tells when to stop, and the recursive steps tell how the function will call itself.

Recursive Function in C

data_type function_name (argument)

{

//base condition

//Recursion steps

//return statements

}

Working on Recursion In C

Let us consider a Fibonacci problem in C. In this problem, we will have a series of numbers in which each is the sum of two preceding numbers. It usually starts with 0 and 1. The mathematical formula for the Fibonacci series is given by.

F (n) = F (n-1) + F(n-2)

The starting value for the F(0) is 0, and F(1) is 1. Let us check the implementation of Fibonacci series in the table below using recursion in C.

Recursion in C

#include<stdio.h>

int fibonacci(int);

void main ( )

{

int n,f;

printf(“Enter the value of n?”);

scanf(“%d”,&n);

f = fibonacci(n);

printf(“%d”,f);

}

int fibonacci (int n)

{

if (n==0)

{

return 0;

}

else if (n == 1)

{

return 1;

}

else

{

return fibonacci(n-1)+fibonacci(n-2);

}

Step 1: Suppose we pass 5 as an argument in the Fibonacci function. The first recursion call will be made for fibonacci (5). It will check the base condition, which it does not satisfy. Hence, it calls the function for fibonacci (4)+ fibonacci (3)

Step 2: Again, the fibonacci (4) and fibonacci (3) begin execution, it calls fibonacci (n-1)+fibonacci (n-2) until the base condition is met.

Step 3: This recursion calls will keep on coming until the base condition which is n=1 or 0, is not met.

At last, the recursion calls will return 5, which returns the fifth number in the Fibonacci series. These recursive calls run until the base condition is met.

Recommended Course

Basics Of Recursive Function In C

The recursive function in C consists of two important terms. It is important to define the base condition and recursive steps while defining the recursive function.

1. Base Condition

The base condition is important in Recursion in C. It tells the recursive function when to terminate. If we fail to use a correct base function, then our function may give wrong output or may run for infinite time.

In the above example of fibonacci series we used n=1 and n=0 for base condition.

Recursion in C

if ( n==1){

return 1;

}

if (n==0 ) {

return 0;

}

Here, the function calls will terminate when the value of N become 1 or 0.

2. Recursive Steps

This step defines the workings of recursive functions. It tells which type of recursion will take place in executing the problem. In this step, our problem will be divided into small, similar subproblems, which will be executed one by one.

In the Fibonacci series above, we used the recursive steps given below.

Recursion in C

fibonacci (n-1) + fibonacci (n-2)

This recursive function call is also known as recurrence relation in Computer science.

Types of Recursion in C

There are mainly two types of recursion in C given below.

1. Direct Recursion: A direct recursion occurs when a function calls itself directly during execution.

Let us understand direct recursion with an example.

Recursion in C

#include <stdio.h>

Void fun (int n) {

if (n > 0) {

printf(“%d “, n);

fun (n – 1);

}

int main() {

int num = 5;

fun (num);

return 0;

}

In the above example, recursion functions call themselves directly in the function.

2. Indirect Recursion: The indirect Recursion in C takes place when two or more functions calls itself each other in a cycle. Here, check that function A calls function B.

Recursion in C

#include <stdio.h>

void functionB (int n);

void functionA(int n) {

if (n > 0) {

printf(“%d “, n);

functionB(n – 1); // Indirectly calling functionB

}

void functionB(int n) {

if (n > 1) {

printf(“%d “, n);

functionA(n / 2); // Indirectly calling functionA

}

int main() {

int num = 10;

printf(“Indirect Recursion: “);

functionA(num);

return 0;

}

The above function demonstrates the working of an indirect function in C language.

Recursion in C Memory Allocation

In Recursion, the function calls are stored in stack memory until the function executes a base condition or returns some value. In stacks, recursion calls are stored at the top of the stack each time they are called. It will continue collecting inside the stack until a return value is encountered.

The compiler maintains a pointer at the top of the stack where the return value will be stored after execution. When all the recursion function calls are complete, we execute the base function and start returning the call to the caller function.

Let us take an example of a factorial function in C. First let us implement factorials in C using recursion.

Recursion In C

// C program to find the factorial of a given number

#include <stdio.h>

unsigned int factorial (unsigned int n)

{

if (n == 1)

{

return 1;

}

return n * factorial (n – 1);

}

// Driver code

int main()

{

int num = 4;

printf (“Factorial of %d is %d”, num, factorial(num));

return 0;

}

Step1: Let us find the factorial of a number 4 using the above code.

factorial (4)

Step 2: Now, the factorial 4 will call the function using its recursive relation.

factorial (4) 4*factorial(3)

Step 3:

factorial (4) 4*factorial(3) 3* factorial (2)

Step 4:

factorial (4) 4*factorial(3) 3* factorial (2) 2*factorial (1)

Step 5: Now, the value of N is 1, which is the base condition of the function. Now, factorial (1) will return 1.

factorial (4) 4*factorial(3) 3* factorial (2) 2

Step 6:

factorial (4) 4*factorial(3) 3*2(6)

Step 7:

factorial (4) 4*6(24)

Now, the factorial (4) will return 24 as the result, and the stack gets empty and destroyed.

Examples of Recursion in C

Let us now check some examples of recursion function in C.

Example 1: Write a program to find the factorial of a number using recursion in C.

Recursion in C

// C program to find the factorail using tail recursion

#include <stdio.h>

int factorialTail(int n)

{

// Base case

if (n == 1 || n == 0) {

return 1;

}

else {

// Tail recursive call

return n * factorialTail(n – 1);

}

int main()

{

int n = 5;

int fact1 = factorialTail(n);

printf(“Resursive Factorial of %d: %d \n”, n, fact1);

return 0;

}

Example 2: Program to find Greatest Common Divisor using recursion in C

Recursion in C

#include <stdio.h>

int gcd(int a, int b) {

if (b == 0) {

return a;

}

return gcd(b, a % b);

}

int main() {

int result = gcd(24, 32);

printf(“The GCD of 24 and 32 is: %d\n”, result);

return 0;

}

Recursion in C FAQs

Q1. What is recursion in C language?

Ans: Recursion in C is the process of solving a problem using repeated function calls until a particular condition is met directly or indirectly.

Q2. How many types of recursion are there in C langauge?

Ans: Let us check the type of recursion in C .

1. Direct Recursion

2. Indirect Recursion

3. Head Recursion

4. Tail Recursion

Q3. What is the use of Recursion in C programming?

Ans: Recursion helps to solve a complex problem into many small subproblems and simplifies the code. Check the article for more details on recursion in C.

Q4. Is recursion hard to understand?

Ans: Yes, many programmers find recursion difficult to understand. However, if you follow the recursion in C fundamentals, you can easily understand Recursion.