EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 600+ Courses All in One Bundle
  • Login

Recursive Function in C

Home » Software Development » Software Development Tutorials » C Programming Tutorial » Recursive Function in C

Recursive Function in C

Introduction to Recursive Function in C

The process of repeating the items in a similar way as it was before is known as recursion. A function is said to be recursive if it is called within itself. Recursion is supported by the programming language C. Below are two conditions that are critical for implementing recursion in C:

  • An exit condition: This condition helps the function to identify when to exit that function. In case we do not specify the exit condition then the code will enter into an infinite loop.
  • Changing the counter: Changing the counter in every call to that function.

In this way, we can implement a recursive function in the C programming language. These functions are useful for solving money mathematical problems that require a similar process to be called several times. Examples of such problems are calculating the factorial of a number of Fibonacci series generation.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

Syntax:

int  fun(a1)
{
If(base_condition) return val;
fun(a2);
}

How Recursive Function Works in C?

Recursive functions are the way to implement the equation in C programming language. A recursive function is called with an argument passed into it say n, memory in the stack is allocated to the local variables as well as the functions. All the operations present in the function are performed using that memory. The condition for exit is checked if it fulfills. When compiler detects a call to another function it immediately allocates new memory on the top of the stack where a different copy of the same local variables and the function gets created. Enter the same process continues.

When the base condition returns true, the particular value passed to the calling function. The memory allocated to that function gets cleared. similarly, the new value gets calculated in the calling function and IT returns to the super calling function. This way recursive calls are made to the function delete reaches the first function and the whole stack memory gets cleared and output is returned. Incase base condition or exit condition is not specified in the function then recursive calls to the function can lead to an infinite loop.

Example of Recursive Function

Now we will be going to see the examples of Recursive Function in C

Code:

#include <stdio.h>
int  fun(int n)
{
if(n==1) return 1 ; //exit or base condition which gives an idea when to exit this loop.
return n*fun(n-1); //function is called with n-1 as  it's argument .
//The value returned is multiplied with the argument passed in calling function.
}
int main(){
int test=4;
int result =0;
result =fun(test);
printf("%d",result);//prints the output result.
}

Popular Course in this category
C Programming Training (3 Courses, 5 Project)3 Online Courses | 5 Hands-on Projects | 34+ Hours | Verifiable Certificate of Completion | Lifetime Access
4.5 (5,617 ratings)
Course Price

View Course

Related Courses
C++ Training (4 Courses, 5 Projects, 4 Quizzes)Java Training (40 Courses, 29 Projects, 4 Quizzes)

Output:

Recursive Function in C

Explanation of Above Code

The above-given example is of finding the factorial of a number. When the main function calls fun(4) then first the exit condition (4==1) is checked then 4*fun(3) is called. Again base condition (3==1) gets checked. Similarly, it will return 3*fun(2) is called and this continues up to 2*fun(1)  is called and where it meets the base condition and returns 1 then calling function returns 2*1 then,3*2*1 and from the first call 4*3*2*1 is returned. Thus result in main function stores 24 and prints that on output.

Memory Allocation of Recursive Function

Each call to a function in c language results in memory allocation on the top of a stack. When a recursive function is called memory is allocated to it on the top of the memory that has been allocated to the calling function with all the different copy of local variables are created for each call to the function.
What is the base condition is reached, the memory allocated to the function gets destroyed and pointer returns to the calling function? this process is repeated then the first calling function and at last, the stack memory gets empty.

 In the above-given example to calculate the factorial of a number below is the scenario for memory allocation.

Step – 1  

Recursive Function in C step1

Step – 2

Recursive Function in C step2

Step – 3

Recursive Function in C step3

Step – 4

step4

Step – 5

step5

Step – 6

step4

Step – 7

Recursive Function in C step3

Step – 8

Recursive Function in C step2

Step – 9

step 9

Types of Recursion

There are two types of recursion in C programming that are given below:

1. Tail and Non-Tailed Recursion

The above-given type of recursion is explained below:

  • Tail Recursion 

It is a type of recursive function recursion call in the function that is the last action to be done in the definition of the function. Means recursive call occurs after everything else logic in the function gets implemented.

Using a tail recursion in our program in hansis the performance of the program and also reduces the memory usage of so function. It is so because as other logic in the function has been implemented to the memory allocated to the calling function can be removed from the stack and reused.

Code:

int fun1(n){
printf(“the result is “);
return fun1(n-1);
}
void main()
{
fun1(4);
}

  • Non-Tailed Recursion

This type of recursion recursive collage made in the middle of the function definition. Men’s pants recursion is completed and the values returned to the calling function there are more steps to be performed thus the memory cannot be cleared.

Code:

int fun1(n){
printf(“the result is “);
return n* fun1(n-1);
}
void main(){
fun1(4);
}

2. Direct and Indirect Recursion

The above-given type of recursion is explained below:

  • Indirect Recursion

Indirect recursion is said to occur when a particular function is called in recursive way medium of another function.

Code:

int fun1(){
fun2();
}
int fun2(){
fun1(); // calling the procedure recursively using another function.
}
void main(){
fun1();
}

  • Direct Recursion

Direct recursion is said to occur when the recursive call to the function is made within its own definition.’

Code:

int fun1(){
fun1();
}
void main(){
fun1();
}

Conclusion

It can easily be concluded that recursive functions are at most important for solving mathematical problems that require a similar method all logic to be implemented repeatedly until an exit condition is met. Many problems such as towers of Hanoi, tree traversals, calculating the depth of graphs.

It is important to mention a base condition for the recursive function. Memory and time requirements are greater for the recursive program as compared to the iterative ones, thus must be used carefully.

Recommended Articles

This is a guide to Recursive Function in C. Here we discuss the basic concept, working, types, memory allocation and examples of  Recursive Function in C. You may also look at the following articles to learn more –

  1. Arrays in C Programming
  2. Palindrome in C Program
  3. Patterns in C Programming
  4. Difference Between C vs C++

C Programming Training (3 Courses, 5 Project)

3 Online Courses

5 Hands-on Projects

34+ Hours

Verifiable Certificate of Completion

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
C Programming Tutorial
  • Function
    • Math Functions in C
    • Hashing Function in C
    • Recursive Function in C
    • Power Function in C
    • fputs in C
    • C puts() Function
    • fprintf() in C
    • fseek() in C
    • Stderr in C
    • ASCII Value in C
    • strcat() in C
    • Inline Function in C
    • sizeof() in C
    • Function Prototype in C
    • C ftell()
  • Basic
    • Introduction to C
    • What is C
    • Career in C Programming
    • Advantages of C
    • How to Install C
    • Best C Compilers
    • Data Types in C
    • Variables in C
    • C Keywords
    • C Command
    • Command Line Arguments in C
    • C Literals
    • Constants in C
    • Unsigned Int in C
    • String in C
  • Pointers
    • Pointers in C
    • Null pointer in C
    • Function Pointer in C
    • Double Pointer in C
    • Void Pointer in C
    • Const Pointer in C
    • Dangling Pointers in C
    • Pointer Arithmetic in C
  • Operators
    • C Operators
    • Arithmetic Operators in C
    • Relational Operators in C
    • Assignment Operators in C
    • Logical Operators in C
    • Conditional Operator in C
    • Modulus Operator in C
    • Ternary Operator in C
    • Address Operator in C
    • Unary Operator in C
    • Operators Precedence in C
    • Left Shift Operator in C
  • Control Statement
    • Control Statements in C
    • If Statement in C
    • If-else Statement in C
    • Else if Statement in C
    • Nested if Statement in C
    • #else in C
    • Structure Padding in C
    • Nested Structure in C
    • Continue Statement in C
    • Break Statement in C
    • Switch Statement in C
    • Goto Statement in C
  • Loops
    • Loops in C
    • For Loop in C
    • While Loop in C
    • Do While Loop in C
    • Nested Loop in C
    • Infinite Loop in C 
  • Array
    • Arrays in C Programming
    • 2-D Arrays in C
    • 3D Arrays in C
    • Multidimensional Array in C
    • Array Functions in C
    • Strings Array in C
  • Sorting
    • Sorting in C
    • Heap Sort in C
  • Advanced
    • Constructor in C
    • Encapsulation in C
    • C Storage Classes
    • Static Keyword in C
    • File Handling in C
    • Queue in C
    • Hexadecimal in C 
    • typedef in C
    • Memory Allocation in C
    • Linked List in C
    • Volatile in C
    • Tokens in C
    • Expression in C
    • Regular Expression in C
    • Error Handling in C
    • Types of Errors in C
    • Preprocessor in C
    • Preprocessor Directives in C
    • fscanf() in C
    • #Pragma in C
    • #ifndef in C
    • #undef in C
    • Macros in C
  • C programs
    • Patterns in C Programming
    • Star Patterns in C
    • Number Patterns in C
    • Swapping in C
    • Reverse Number in C
    • Palindrome in C Program
    • Factorial in C
    • Fibonacci Series in C
    • Square Root in C
    • Random Number Generator in C
    • Prime Numbers in C
    • Escape Sequence in C
    • Reverse String in C
    • Leap Year Program in C
    • Anagram Program in C
    • Strong Number in C
    • String Concatenation in C
    • C Programming Matrix Multiplication
    • Decimal to Octal in C
    • Expression Evaluation in C
    • Decimal to Hexadecimal in C
  • Interview question
    • C Programming Interview Questions

Related Courses

C Programming Training Course

C++ Training Course

Java Training Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - C Programming Training (3 Courses, 5 Project) Learn More