L17 Recursion Practice Set (Questions)

Topics covered in the lecture:
● Recursive programs on factorial, fibonacci

● Comparing recursive and iterative solutions
Practice/Tutorial Questions:
Some output/error finding/mcq type questions for practice:

1. Which of the following correctly describes a characteristic of recursion?
a. It always requires more memory than iteration.
b. It never uses the call stack.
c. Recursive solutions are always faster than iterative ones.
d. Recursive functions do not need a base case.
2. What does the following code do?

def mystery(n):
if n == 0:
return 0
else:
return n + mystery(n - 1)
print(mystery(5))
3. What does the following code do?

def mystery(n):
if n == 0:
return 0
elif n % 2 == 0:
return n + mystery(n - 2)
else:
return mystery(n - 1)
4. What would be the output of the following code?

def countdown(n):
if n == 0:
return
print(n, end=" ")
countdown(n - 1)
print(n, end=" ")
countdown(3)
5. What would be the output of the following code?

def zigzag(n):
if n == 0:
return
print(n, end=" ")
zigzag(n - 1)
print(n, end=" ")
zigzag(n - 1)
zigzag(3)
6. Identify the error in the following recursive function designed to check if an

array is sorted in ascending order and write the correct code.
def is_sorted(arr, index):

if index == len(arr) - 1:
return True
elif arr[index] > arr[index + 1]:
return False
else:
is_sorted(arr, index + 1)
7. How many times will the base case execute if nested_calls(4) is called?
def nested_calls(n):
if n == 0:
return 1
nested_calls(n - 1)
nested_calls(n - 1)
nested_calls(4)
Programming Questions:
1. Sum of Digits (Trick with Negative Numbers): Write a recursive function
that computes the sum of digits of an integer n. Handle cases where the
number is negative and ensure the recursive function works properly.
Test cases:
Input1: 123
Output1: 6
Input2: -123
Output2 : 6
2. Write a recursive function to find the maximum element in a list.

Test case:
Input: [3, 1, 4, 1, 5, 9, 2, 6, 5]
Output: 9
3. Write a recursive function to print all subsequences of a given string. This is

trickier because it involves managing both inclusion and exclusion at each
step.
Test case:
Input: “abc”
Output:
c
b
bc
a
ac
ab
abc
4. Write a recursive function to count the number of times a particular

character appears in a string
Test case 1:
String: hello world
Character: o
Output: 2
Test case 2:
String: abcabcabc
Character: b
Output: 3
5. Write a recursive function to generate all permutations of a string

Test case:
String: ‘abc’
Output: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
6. Write a recursive function to print the power set of a given set

Test case:
Input: {1, 2, 3}
Output:
{frozenset({2}), frozenset({2, 3}), frozenset({1, 2, 3}), frozenset({1, 2}),
frozenset({3}), frozenset({1}), frozenset(), frozenset({1, 3})}
7. Write a recursive function to flatten a nested list

Test case:
Input: [1, [2, 3], 4, [5, [6, 7]], 8, [[[1],2,3],4],5]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5]
Some scenario-based questions:

1. Parentheses Matching using Recursion: You are given a mathematical
expression containing variables, operators, and parentheses. Write a
function is_balanced_expression(s: str) -> bool that checks whether the
parentheses in the expression are balanced.
The expression will contain:
● Parentheses ( and ).
● Variables (e.g., a, b, x), digits, and operators (e.g., +, -, *, /).
The parentheses are considered balanced if:
● Every opening parenthesis ( has a corresponding closing parenthesis ).

● Parentheses are properly nested.
Example Test Cases:
test_cases = [
"a + b(c - d) * e", # Balanced: True
"a + (b - c * d", # Unbalanced: False
"x + y - (z + w)", # Balanced: True
"((a + b) * (c - d))", # Balanced: True
"(a + b)) * (c - d)", # Unbalanced: False
"a + b * (x + y) - (z * w)",# Balanced: True
"((a + b) * c + (d / e))", # Balanced: True
"(a + b) * c + (d - e", # Unbalanced: False

]
Constraints:
The string s contains at most 10^5 characters and only valid characters
(parentheses, digits, operators, and variables).
2. The Subset Sum Problem: You are tasked with helping a store manager
organize a promotional sale. The store has a collection of products, each with
a specific price, and the manager wants to know if there exists a combination
of products that can be purchased for exactly a target budget.
Write a recursive function that takes a list of product prices and a target
budget as input. The function should return one subset of products whose
total price equals the target budget. If no such combination exists, return an
appropriate message.
For example:
● Given the list of product prices [3, 34, 4, 12, 5, 2] and a target
budget of 9, the function should output a subset like [4, 5], as 4 +
5 = 9.
● If the target budget is not achievable, print No subset found for
the given budget.
Test case 1:
nums = [3, 34, 4, 12, 5, 2]
target = 9
find_subset_sum(nums, target)
# Output: Subset that forms the sum: [4, 5]
Test case 2:
nums = [3, 34, 4, 12, 5, 2]
target = 30
find_subset_sum(nums, target)
# Output: No subset found for the given budget.

L17 Recursion Practice Set (Questions)

Uploaded by

Copyright:

Available Formats

L17 Recursion Practice Set (Questions)

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

L17 Recursion Practice Set (Questions)

Uploaded by

Copyright:

Available Formats

Topics covered in the lecture:

● Recursive programs on factorial, fibonacci

Some output/error finding/mcq type questions for practice:

2. What does the following code do?

3. What does the following code do?

4. What would be the output of the following code?

5. What would be the output of the following code?

6. Identify the error in the following recursive function designed to check if an

def is_sorted(arr, index):

2. Write a recursive function to find the maximum element in a list.

3. Write a recursive function to print all subsequences of a given string. This is

4. Write a recursive function to count the number of times a particular

5. Write a recursive function to generate all permutations of a string

6. Write a recursive function to print the power set of a given set

7. Write a recursive function to flatten a nested list

Some scenario-based questions:

The expression will contain:

The parentheses are considered balanced if:

● Every opening parenthesis ( has a corresponding closing parenthesis ).

Example Test Cases:

"a + b(c - d) * e", # Balanced: True

"a + (b - c * d", # Unbalanced: False

"x + y - (z + w)", # Balanced: True

"((a + b) * (c - d))", # Balanced: True

"(a + b)) * (c - d)", # Unbalanced: False

"a + b * (x + y) - (z * w)",# Balanced: True

"((a + b) * c + (d / e))", # Balanced: True

"(a + b) * c + (d - e", # Unbalanced: False

nums = [3, 34, 4, 12, 5, 2]

nums = [3, 34, 4, 12, 5, 2]

# Output: No subset found for the given budget.

You might also like