Recursion in C

What is Recursion?

Recursion means a function calling itself repeatedly. Every recursive function has two parts:

• Base Case – condition where recursion stops
• Recursive Case – function calls itself

void fun(){
    if(condition) return;   // base case
    fun();                  // recursive call
}

Why Recursion?

• Solves problems that are naturally repetitive
• Useful in mathematical computations
• Essential for tree/graph algorithms
• Simplifies complex logic

When to Use Recursion?

• Factorial calculation
• Fibonacci series
• Sum of digits
• Searching in trees
• Tower of Hanoi
• Backtracking problems

Rules of Recursion

• Must have a base case
• Each recursive call should move towards the base case
• Avoid deep recursion (stack overflow)
• Prefer iteration if recursion gets too heavy

Recursion Examples

Example 1 – Print Numbers from 1 to N

#include <stdio.h>

void print(int n){
    if(n == 0) return;
    print(n - 1);
    printf("%d ", n);
}

int main(){
    print(5);
    return 0;
}

Example 2 – Factorial Using Recursion

#include <stdio.h>

int fact(int n){
    if(n == 0) return 1;
    return n * fact(n - 1);
}

int main(){
    printf("%d", fact(5));
    return 0;
}

Example 3 – Sum of First N Numbers

#include <stdio.h>

int sum(int n){
    if(n == 0) return 0;
    return n + sum(n - 1);
}

int main(){
    printf("%d", sum(10));
    return 0;
}

Example 4 – Fibonacci Using Recursion

#include <stdio.h>

int fib(int n){
    if(n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

int main(){
    printf("%d", fib(6));
    return 0;
}

Example 5 – Reverse Digits Using Recursion

#include <stdio.h>

void reverse(int n){
    if(n == 0) return;
    printf("%d", n % 10);
    reverse(n / 10);
}

int main(){
    reverse(1234);
    return 0;
}

Advantages of Recursion

• Cleaner and more readable code
• Solves problems that are naturally recursive
• Best for hierarchical and tree-like structures

Disadvantages of Recursion

• Consumes more memory (stack frames)
• Slower than loops
• Risk of infinite recursion if base case is wrong

15 Recursion Examples

/* 1. Print numbers 1 to n */
#include <stdio.h>
void print(int n){
    if(n==0) return;
    print(n-1);
    printf("%d ", n);
}
int main(){ print(5); }

/* 2. Factorial */
#include <stdio.h>
int fact(int n){
    if(n<=1) return 1;
    return n * fact(n-1);
}
int main(){ printf("%d", fact(5)); }

/* 3. Fibonacci */
#include <stdio.h>
int fib(int n){
    if(n<=1) return n;
    return fib(n-1)+fib(n-2);
}
int main(){ printf("%d", fib(6)); }

/* 4. Sum of numbers */
#include <stdio.h>
int sum(int n){
    if(n==0) return 0;
    return n + sum(n-1);
}
int main(){ printf("%d", sum(10)); }

/* 5. Reverse a number */
#include <stdio.h>
int rev(int n, int r){
    if(n==0) return r;
    return rev(n/10, r*10 + n%10);
}
int main(){ printf("%d", rev(1234,0)); }

/* 6. Count digits */
#include <stdio.h>
int digits(int n){
    if(n==0) return 0;
    return 1 + digits(n/10);
}
int main(){ printf("%d", digits(7865)); }

/* 7. Power function */
#include <stdio.h>
int power(int a,int b){
    if(b==0) return 1;
    return a * power(a,b-1);
}
int main(){ printf("%d", power(2,5)); }

/* 8. Greatest Common Divisor */
#include <stdio.h>
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){ printf("%d", gcd(48,18)); }

/* 9. Print array using recursion */
#include <stdio.h>
void show(int arr[], int i, int n){
    if(i==n) return;
    printf("%d ", arr[i]);
    show(arr,i+1,n);
}
int main(){
    int a[]={1,2,3,4};
    show(a,0,4);
}

/* 10. Check if string is palindrome */
#include <stdio.h>
#include <string.h>
int pal(char s[], int l, int r){
    if(l>=r) return 1;
    if(s[l]!=s[r]) return 0;
    return pal(s,l+1,r-1);
}
int main(){
    char s[]="level";
    printf("%d", pal(s,0,strlen(s)-1));
}

/* 11. Binary search recursion */
#include <stdio.h>
int bs(int a[],int l,int r,int key){
    if(l>r) return -1;
    int m=(l+r)/2;
    if(a[m]==key) return m;
    if(key< a[m]) return bs(a,l,m-1,key);
    return bs(a,m+1,r,key);
}
int main(){
    int a[]={1,3,5,7,9};
    printf("%d", bs(a,0,4,7));
}

/* 12. Print digits separately */
#include <stdio.h>
void printDigits(int n){
    if(n==0) return;
    printDigits(n/10);
    printf("%d ", n%10);
}
int main(){ printDigits(5421); }

/* 13. Multiply using repeated addition */
#include <stdio.h>
int mul(int a,int b){
    if(b==0) return 0;
    return a + mul(a,b-1);
}
int main(){ printf("%d", mul(6,4)); }

/* 14. Minimum element in array */
#include <stdio.h>
int findMin(int a[],int i,int n){
    if(i==n-1) return a[i];
    int m=findMin(a,i+1,n);
    return (a[i]< m)?a[i]:m;
}
int main(){
    int a[]={9,4,7,2,8};
    printf("%d", findMin(a,0,5));
}

/* 15. Count vowels using recursion */
#include <stdio.h>
int vowel(char *s){
    if(*s=='\0') return 0;
    int v = (*s=='a'||*s=='e'||*s=='i'||*s=='o'||*s=='u'||
             *s=='A'||*s=='E'||*s=='I'||*s=='O'||*s=='U');
    return v + vowel(s+1);
}
int main(){ printf("%d", vowel("Sourav Sahu")); }

Practice Questions

1. What is recursion? Write its two main parts.
2. Explain base case with an example.
3. Difference between recursion and iteration?
4. Write recursive function to calculate factorial.
5. Write recursive function to count digits.

Practice Task