Recursion in Python
What is Recursion in Python with syntax and example?
In simple words, Recursion is a process where a function calls itself and falls in an infinite loop until a particular condition breaks that infinite loop.
Recursion in Python is a process where a function calls itself directly or indirectly to solve a smaller instance of the same problem until it reaches a base condition, which stops the recursive calls.
Syntax:
def recursive_function(parameters):
if base_condition:
return result
else:
return recursive_function(modified_parameters)
Example (Factorial Calculation):
def factorial(n):
if n == 0: # base condition
return 1
else:
return n * factorial(n - 1) # recursive call
print(factorial(5))
Output:
120
Explanation:
22+ questions with answers and examples to help understand recursion deeply in Python
Question 1. Why do we need recursion in Python?
Answer: Recursion lets us solve complex problems by breaking them into smaller, simpler sub-problems.
Example:
def factorial(n):
if n == 0: return 1
return n * factorial(n - 1)
print(factorial(5))
Output:
120
Question 2. When is recursion useful?
Answer: Recursion is helpful for problems with repetitive, self-similar structure, like navigating nested folders.
Example:
def folder_depth(folder):
if not isinstance(folder, list): return 0
return 1 + max((folder_depth(sub) for sub in folder), default=0)
print(folder_depth([1, [2, [3, 4], 5]]))
Output:
3
Question 3. Calculate Sum of Natural Numbers Up to N
Explanation: Add numbers from 1 to N recursively.
Example:
def sum_n(n):
if n == 0:
return 0
return n + sum_n(n - 1)
print(sum_n(5))
Output:
15
Question 4. Check if a String is a Palindrome
Explanation: Compare first and last characters recursively.
Example:
def is_palindrome(s):
if len(s) < 2:
return True
return s[0] == s[-1] and is_palindrome(s[1:-1])
print(is_palindrome("radar"))
Output:
True
Question 5. Calculate the Power of a Number
Explanation: Multiply base n times, recursively decreasing exponent.
Example:
def power(base, exp):
if exp == 0:
return 1
return base * power(base, exp - 1)
print(power(2, 3))
Output:
8
Question 6. Find GCD of Two Numbers
Explanation: Use Euclidean algorithm to reduce numbers recursively.
Example:
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
print(gcd(48, 18))
Output:
6
Question 7. Generate Fibonacci Series Up to N Terms
Explanation: Add previous two terms recursively to generate each term.
Example:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print([fibonacci(i) for i in range(6)])
Output:
[0, 1, 1, 2, 3, 5]
Question 8. Calculate Product of List Elements
Explanation: Multiply each element recursively by moving through the list.
Example:
def product(lst):
if not lst:
return 1
return lst[0] * product(lst[1:])
print(product([1, 2, 3, 4]))
Output:
24
Question 9. Reverse a String Using Recursion
Explanation: Reverse string by calling recursively with sliced parts.
Example:
def reverse(s):
if len(s) <= 1:
return s
return reverse(s[1:]) + s[0]
print(reverse("hello"))
Output:
olleh
Question 10. Count Occurrences of a Character in a String
Explanation: Increment count if first character matches, move to next.
Example:
def count_char(s, char):
if not s:
return 0
return (s[0] == char) + count_char(s[1:], char)
print(count_char("recursion", "r"))
Output:
2
Question 11. Flatten a Nested List
Explanation: Flatten by recursively merging nested lists.
python
Example:
def flatten(lst):
if not lst:
return []
if isinstance(lst[0], list):
return flatten(lst[0]) + flatten(lst[1:])
return [lst[0]] + flatten(lst[1:])
print(flatten([1, [2, [3, 4], 5]]))
Output:
[1, 2, 3, 4, 5]
Question 12. Sum of Digits in a Number
Explanation: Add last digit and recurse with remaining digits.
Example:
def sum_digits(n):
if n == 0:
return 0
return n % 10 + sum_digits(n // 10)
print(sum_digits(123))
Output:
6
Question 13. Binary Representation of a Number
Explanation: Find binary digits recursively by dividing by 2.
Example:
def to_binary(n):
if n == 0:
return ""
return to_binary(n // 2) + str(n % 2)
print(to_binary(10))
Output:
1010
Question 14. Calculate Minimum Element in a List
Explanation: Compare each element recursively to find minimum.
Example:
def find_min(lst):
if len(lst) == 1:
return lst[0]
return min(lst[0], find_min(lst[1:]))
print(find_min([4, 2, 7, 1]))
Output:
1
Question 15. Tower of Hanoi Problem
Explanation: Solve by moving discs between pegs recursively.
Example:
def hanoi(n, source, target, auxiliary):
if n > 0:
hanoi(n - 1, source, auxiliary, target)
print(f"Move disc from {source} to {target}")
hanoi(n - 1, auxiliary, target, source)
hanoi(2, 'A', 'C', 'B')
Output:
Move disc from A to B
Move disc from A to C
Move disc from B to C
Question 16. Remove All Occurrences of a Character from a String
Explanation: Skip character and recurse with the rest of the string.
Example:
def remove_char(s, char):
if not s:
return ""
return ("" if s[0] == char else s[0]) + remove_char(s[1:], char)
print(remove_char("hello", "l"))
Output:
heo
Question 17. Find Factorial Using Recursion
Explanation: Multiply current n with factorial(n - 1).
Example:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(5))
Output:
120
Question 18. Print All Permutations of a String
Explanation: Generate permutations by swapping characters recursively.
Example:
def permute(s, answer=""):
if len(s) == 0:
print(answer)
for i in range(len(s)):
permute(s[:i] + s[i+1:], answer + s[i])
permute("abc")
Output:
abc
acb
bac
bca
cab
cba
Question 19. Calculate nth Triangular Number
Explanation: Add current number n and recurse to n-1.
Example:
def triangular(n):
if n == 0:
return 0
return n + triangular(n - 1)
print(triangular(4))
Output:
10
Question 20. Generate a List of Odd Numbers up to N
Explanation: Add number if odd and recurse with remaining numbers.
Example:
def odd_numbers(n):
if n < 1:
return []
if n % 2 == 1:
return odd_numbers(n - 1) + [n]
return odd_numbers(n - 1)
print(odd_numbers(10))
Output:
[1, 3, 5, 7, 9]
Question 21. Find Maximum Depth of a Nested List
Explanation: Calculate depth by recursively examining each element.
Example:
def max_depth(lst):
if not isinstance(lst, list):
return 0
return 1 + max([max_depth(x) for x in lst], default=0)
print(max_depth([1, [2, [3, 4], 5]]))
Output:
3
Question 22. Generate a List of Powers of 2 up to N
Explanation: Calculate powers of 2 recursively until reaching 2^N.
Example:
def powers_of_two(n):
if n < 0:
return []
return powers_of_two(n - 1) + [2 ** n]
print(powers_of_two(3))
Output:
[1, 2, 4, 8]
Tags:
Leave a comment
You must be logged in to post a comment.