Recursion in C - TechStudy

What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. It's useful for problems that can be broken down into smaller, similar subproblems.

Recursion Kya Hai? (Hinglish)

Recursion ek programming technique hai jahan ek function khud ko call karta hai problem solve karne ke liye. Ye un problems ke liye useful hai jo chote, similar subproblems mein break ho sakte hain.

Recursive Function Components

Component	Description	Example
Base Case	Condition to stop recursion	if (n == 0) return 1;
Recursive Case	Function calls itself	return n * factorial(n-1);
Stack	Memory for function calls	Function call stack

Example Program

#include 

// Factorial using recursion
int factorial(int n) {
    // Base case
    if (n == 0 || n == 1) {
        return 1;
    }
    // Recursive case
    return n * factorial(n - 1);
}

// Fibonacci using recursion
int fibonacci(int n) {
    // Base cases
    if (n == 0) return 0;
    if (n == 1) return 1;
    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// Binary search using recursion
int binarySearch(int arr[], int low, int high, int target) {
    if (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] > target) {
            return binarySearch(arr, low, mid - 1, target);
        }
        return binarySearch(arr, mid + 1, high, target);
    }
    return -1;
}

int main() {
    // Factorial example
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    
    // Fibonacci example
    printf("Fibonacci sequence up to %d:\n", num);
    for (int i = 0; i <= num; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    
    // Binary search example
    int arr[] = {2, 4, 6, 8, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 6;
    int result = binarySearch(arr, 0, size - 1, target);
    if (result != -1) {
        printf("Element found at index %d\n", result);
    } else {
        printf("Element not found\n");
    }
    
    return 0;
}

Program Explanation (Hinglish)

Is program mein different recursive functions ka use kiya gaya hai:

factorial(): Number ka factorial calculate kar raha hai
fibonacci(): Fibonacci sequence generate kar raha hai
binarySearch(): Sorted array mein element search kar raha hai
Base case: Recursion ko stop karne ke liye condition
Recursive case: Function khud ko call kar raha hai

Important Points

Every recursive function needs a base case
Recursion uses more memory than iteration
Stack overflow can occur with deep recursion
Some problems are naturally recursive
Tail recursion can be optimized