17. Recursion Problems

রিকার্সন শেখার সবচেয়ে ভালো উপায় হলো বিভিন্ন প্রবলেম সলভ করা। এখানে কিছু জনপ্রিয় রিকার্সন প্রবলেম, তাদের Step-by-Step Logic এবং Complexity Analysis আলোচনা করা হলো।

---

1. ফ্যাক্টোরিয়াল (Factorial)

একটি সংখ্যা n-এর ফ্যাক্টোরিয়াল হলো 1 থেকে n পর্যন্ত সব সংখ্যার গুণফল।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. Base Case: যদি n == 0 বা n == 1 হয়, তবে 1 রিটার্ন করুন।
2. Recursive Case: বর্তমান সংখ্যা n-এর সাথে factorial(n - 1) গুণ করুন।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Time Complexity: O(n) - n বার ফাংশন কল হয়।
• Space Complexity: O(n) - কল স্ট্যাকের জন্য।

Implementation

// Java
public int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

# Python
def factorial(n):
    if n <= 1: return 1
    return n * factorial(n - 1)

---

2. ফিবোনাচ্চি সিরিজ (Fibonacci Series)

সিরিজটি এমন: 0, 1, 1, 2, 3, 5, 8, 13... যেখানে প্রতিটি সংখ্যা তার আগের দুটি সংখ্যার যোগফল।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. Base Case: যদি n == 0 হয়, 0 রিটার্ন করুন। যদি n == 1 হয়, 1 রিটার্ন করুন।
2. Recursive Case: fib(n - 1) + fib(n - 2) রিটার্ন করুন।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Time Complexity: O(2^n) - এটি এক্সপোনেনশিয়াল (Exponential), কারণ প্রতিটি কলে দুটি করে নতুন কল হয়।
• Space Complexity: O(n) - স্ট্যাকের গভীরতা n পর্যন্ত যায়।

Implementation

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

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

---

3. সংখ্যার অংকের যোগফল (Sum of Digits)

যেমন: 123 এর ডিজিটগুলোর যোগফল 1+2+3 = 6।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. Base Case: যদি সংখ্যাটি 0 হয়, তবে 0 রিটার্ন করুন।
2. Recursive Case: শেষ ডিজিট (n % 10) নিন এবং বাকি সংখ্যার (n / 10) সাথে যোগ করুন।

Implementation

// Java
public int sumOfDigits(int n) {
    if (n == 0) return 0;
    return (n % 10) + sumOfDigits(n / 10);
}

# Python
def sum_of_digits(n):
    if n == 0: return 0
    return (n % 10) + sum_of_digits(n // 10)

---

4. পাওয়ার ক্যালকুলেশন (Power Calculation - x^n)

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. Base Case: যদি n == 0 হয়, তবে 1 রিটার্ন করুন।
2. Recursive Case: x * power(x, n - 1) রিটার্ন করুন।
3. Optimization: দ্রুত করার জন্য divide and conquer (O(log n)) ব্যবহার করা যায়।

Implementation

// Java
public int power(int x, int n) {
    if (n == 0) return 1;
    return x * power(x, n - 1);
}

# Python
def power(x, n):
    if n == 0: return 1
    return x * power(x, n - 1)

---

5. টাওয়ার অফ হ্যানয় (Tower of Hanoi)

এটি একটি ক্লাসিক্যাল রিকার্সন প্রবলেম যেখানে তিনটি পোল এবং কিছু ডিস্ক থাকে। বড় ডিস্কের ওপর ছোট ডিস্ক সবসময় রাখতে হবে।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. n-1 সংখ্যক ডিস্ককে সোর্স পোল থেকে অক্সিলিয়ারি পোলে সরিয়ে নিন।
2. সবচেয়ে বড় ডিস্কটিকে সোর্স থেকে ডেস্টিনেশন পোলে নিন।
3. এবার n-1 সংখ্যক ডিস্ককে অক্সিলিয়ারি থেকে ডেস্টিনেশন পোলে নিয়ে আসুন।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Time Complexity: O(2^n - 1) - n সংখ্যক ডিস্কের জন্য মুভমেন্ট সংখ্যা।

Implementation

// Java
public void towerOfHanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        System.out.println("Move disk 1 from " + from + " to " + to);
        return;
    }
    towerOfHanoi(n - 1, from, aux, to);
    System.out.println("Move disk " + n + " from " + from + " to " + to);
    towerOfHanoi(n - 1, aux, to, from);
}

# Python
def tower_of_hanoi(n, source, destination, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return
    tower_of_hanoi(n - 1, source, auxiliary, destination)
    print(f"Move disk {n} from {source} to {destination}")
    tower_of_hanoi(n - 1, auxiliary, destination, source)

---

6. 1 থেকে N প্রিন্ট করা (Print 1 to N)

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. Base Case: যদি n == 0 হয়, তবে থামুন।
2. Recursive Case (Head Recursion): প্রথমে print(n-1) কল করুন, তারপর n প্রিন্ট করুন। এটি করলে 1 থেকে N ক্রমে প্রিন্ট হবে।

Implementation

// Java
public void print1ToN(int n) {
    if (n == 0) return;
    print1ToN(n - 1);
    System.out.print(n + " ");
}

# Python
def print_1_to_n(n):
    if n == 0: return
    print_1_to_n(n - 1)
    print(n, end=" ")

---

7. অ্যারের যোগফল (Sum of Array)

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. Base Case: ইনডেক্স যদি শেষ হয়ে যায়, 0 রিটার্ন করুন।
2. Recursive Case: বর্তমান ইনডেক্সের ভ্যালুর সাথে পরের অংশের যোগফল যোগ করুন।

Implementation

// Java
public int arraySum(int[] arr, int n) {
    if (n <= 0) return 0;
    return arraySum(arr, n - 1) + arr[n - 1];
}

# Python
def array_sum(arr, n):
    if n <= 0: return 0
    return array_sum(arr, n - 1) + arr[n - 1]

---

8. স্ট্রিং রিভার্স (Reverse String)

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. Base Case: স্ট্রিং যদি খালি হয়, খালি স্ট্রিং রিটার্ন করুন।
2. Recursive Case: শেষ ক্যারেক্টারটি নিয়ে তার আগে বাকিগুলোর রিভার্স অংশ যোগ করুন।

Implementation

// Java
public String reverseString(String s) {
    if (s.isEmpty()) return s;
    return reverseString(s.substring(1)) + s.charAt(0);
}

# Python
def reverse_string(s):
    if len(s) == 0: return s
    return reverse_string(s[1:]) + s[0]

---

IMPORTANT

রিকার্সন প্রবলেম সলভ করার সময় সব সময় মনে রাখবেন: প্রথমে Base Case চিন্তা করুন, তারপর বড় সমস্যাটিকে কীভাবে একটি ধাপে ছোট করা যায় তা ভাবুন।

---

TIP

ফিবোনাচ্চির মতো এক্সপোনেনশিয়াল প্রবলেমগুলোকে ফাস্ট করার জন্য আমরা পরে Dynamic Programming (DP) শিখব।