🚀 DSA with C – Day 4: Recursion + Factorial + Fibonacci + Array Sum

 

🎯 Goal:

• Understand the concept of Recursion

• Write recursive functions for:

  • Factorial

  • Fibonacci series

  • Sum of array elements

• Compare recursion with iteration

---

🧠 What is Recursion?

A function calling itself to solve a smaller version of the same problem.

🔄 Recursion Structure:

return_type function_name(parameters) {
    if (base_condition)
        return result;
    else
        return function_name(smaller_problem);
}

---

👨‍💻 1. Factorial Using Recursion

#include <stdio.h>

int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

int main() {
    int num;
    printf("Enter a number: ");
    scanf("%d", &num);
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

---

👨‍💻 2. Fibonacci Series Using Recursion

#include <stdio.h>

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

int main() {
    int terms;
    printf("Enter number of terms: ");
    scanf("%d", &terms);
    printf("Fibonacci Series: ");
    for (int i = 0; i < terms; i++) {
        printf("%d ", fibonacci(i));
    }
    return 0;
}

⚠️ Note: Recursive Fibonacci is inefficient for large n – we’ll optimize it later with memoization or iteration.

---

👨‍💻 3. Sum of Array Using Recursion

#include <stdio.h>

int sumArray(int arr[], int n) {
    if (n == 0) return 0;
    return arr[n - 1] + sumArray(arr, n - 1);
}

int main() {
    int arr[100], n;
    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Sum of array = %d\n", sumArray(arr, n));
    return 0;
}

---

🧪 Practice Problems:

1. Find the GCD of two numbers using recursion.

2. Write a recursive function to calculate the power (xⁿ).

3. Reverse an array using recursion.

---

📘 Homework for Day 4:

• Compare iteration vs recursion by writing factorial using loops.

• Try writing Fibonacci with memoization or using a loop.

• LeetCode problem suggestion: Climbing Stairs – this is basically Fibonacci!

---

📅 Day 4 Summary:

• ✅ Understood recursion

• ✅ Implemented factorial, Fibonacci, and sum via recursion

• ✅ Practiced recursive thinking