Programming Resources | Python… on Telegram: “✅ DSA Part 2 – Recursion 🔁🧠 Recursion is when…”

✅ DSA Part 2 – Recursion 🔁🧠

Recursion is when a function calls itself to solve smaller subproblems. It's powerful but needs a base case to avoid infinite loops.

1️⃣ What is Recursion?
A recursive function solves a part of the problem and calls itself on the remaining part.

Basic Python Example:

def countdown(n):
    if n == 0:
        print("Done!")
        return
    print(n)
    countdown(n - 1)

▶️ Counts down from n to 0

2️⃣ Key Parts of Recursion:
• Base case – Stops recursion
• Recursive case – Function calls itself

Java Example – Factorial:

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

C++ Example – Sum of Array:

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

3️⃣ Why Use Recursion?
• Breaks complex problems into simpler ones
• Great for trees, graphs, backtracking, divide conquer

4️⃣ When Not to Use It?
• Large inputs can cause stack overflow
• Use loops if recursion is too deep or inefficient

5️⃣ Practice Task:
✅ Write a recursive function to calculate power (a^b)
✅ Write a function to reverse a string recursively
✅ Try basic Fibonacci using recursion

👇 Solution for Practice Task

✅ 1. Recursive Power Function (a^b)

Python:

def power(a, b):
    if b == 0:
        return 1
    return a * power(a, b - 1)

print(power(2, 3))  # Output: 8

C++:

int power(int a, int b) {
    if (b == 0) return 1;
    return a * power(a, b - 1);
}
// Example: cout << power(2, 3); // Output: 8

Java:

int power(int a, int b) {
    if (b == 0) return 1;
    return a * power(a, b - 1);
}
// Example: System.out.println(power(2, 3)); // Output: 8

✅ 2. Reverse String Recursively

Python:

def reverse(s):
    if len(s) == 0:
        return ""
    return reverse(s[1:]) + s[0]

print(reverse("hello"))  # Output: "olleh"

C++:

string reverse(string s) {
    if (s.length() == 0) return "";
    return reverse(s.substr(1)) + s[0];
}
// Example: cout << reverse("hello"); // Output: "olleh"

Java:

String reverse(String s) {
    if (s.isEmpty()) return "";
    return reverse(s.substring(1)) + s.charAt(0);
}
// Example: System.out.println(reverse("hello")); // Output: "olleh"

✅ 3. Fibonacci Using Recursion

Python:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(6))  # Output: 8

C++:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
// Example: cout << fib(6); // Output: 8

Java:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
// Example: System.out.println(fib(6)); // Output: 8

*Double Tap ♥️ For More*