Scribd
Upload
16 views4 pages

Recursion Practice Problems and Solutions

The document outlines a series of recursion practice problems categorized into easy, medium, and hard levels, each containing ten problems. It provides examples and formulas for specific problems such as calculating the sum of the first N natural numbers, finding the nth Fibonacci number, and checking if a string is a palindrome. Additionally, it details the base cases and recursive ideas for solving these problems.

Uploaded by

Vishal Masule
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
16 views4 pages

Recursion Practice Problems and Solutions

The document outlines a series of recursion practice problems categorized into easy, medium, and hard levels, each containing ten problems. It provides examples and formulas for specific problems such as calculating the sum of the first N natural numbers, finding the nth Fibonacci number, and checking if a string is a palindrome. Additionally, it details the base cases and recursive ideas for solving these problems.

Uploaded by

Vishal Masule
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

🔹 Recursion Practice

Problems
🟢 Easy (10)

1. Print numbers from 1 to N using recursion.

2. Print numbers from N to 1 using recursion.

3. Find the factorial of a number.

4. Find the sum of first N natural numbers.

5. Find the nth Fibonacci number.

6. Find the sum of digits of a number.

7. Reverse a string using recursion.

8. Check if a string is a palindrome using recursion.

9. Find the greatest common divisor (GCD) of two numbers.

10. Count the number of digits in a number.

🟡 Medium (10)

11. Find the power of a number (x^n) using recursion.

12. Find the product of two numbers using recursion (without *).

13. Print all elements of an array using recursion.

14. Find the maximum element in an array using recursion.

15. Find the minimum element in an array using recursion.

16. Reverse an array using recursion.

17. Count occurrences of a number in an array.

18. Generate all subsets of a string.

19. Generate all binary strings of length N.

20. Tower of Hanoi problem.


🔴 Hard (10)

21. Find all permutations of a string.

22. Solve N-Queens problem.

23. Find all subsets of a set of numbers (power set).

24. Solve the Rat in a Maze problem (backtracking).

25. Word Search in a 2D board using recursion.

26. Find all possible paths from top-left to bottom-right in a matrix.

27. Generate balanced parentheses for given N.

28. Solve Sudoku using recursion and backtracking.

29. Count number of ways to climb stairs (like Fibonacci).

30. Find the longest path in a matrix with given constraints (backtracking).

4. Find the sum of first N natural numbers

 Formula: sum(n) = n + (n-1) + … + 1

 Input: n = 5

 Output: 15 (5+4+3+2+1)

 Idea: Sum(n) = n + Sum(n-1)

 Base case: Sum(0) = 0.

5. Find the nth Fibonacci number

 Series: 0, 1, 1, 2, 3, 5, 8, …

 Definition: F(n) = F(n-1) + F(n-2)

 Base cases: F(0) = 0, F(1) = 1

 Example: F(6) = 8.

6. Find the sum of digits of a number

 Input: n = 1234
 Output: 10 (1+2+3+4)

 Idea: Last digit = n % 10, remaining = n // 10

 Sum(n) = (last digit) + Sum(remaining).

 Base case: When n = 0 → return 0.

7. Reverse a string using recursion

 Input: "hello"

 Output: "olleh"

 Idea: Take last character + reverse(remaining string).

 Base case: Empty string → return empty.

8. Check if a string is a palindrome using recursion

 Input: "madam"

 Output: True (because it reads same forward & backward).

 Idea: Compare first and last characters.

o If they match → check middle substring.

o If not → return false.

 Base case: Empty string or 1 char → true.

9. Find the greatest common divisor (GCD) of two numbers

 Input: (48, 18)

 Output: 6

 Idea: Use Euclidean algorithm:


GCD(a, b) = GCD(b, a % b)

 Base case: If b = 0 → return a.

10. Count the number of digits in a number

 Input: n = 12345
 Output: 5

 Idea: Remove last digit (n // 10) and count.

 Count(n) = 1 + Count(n//10)

 Base case: If n = 0 → return 0.

You might also like