Dynamic Programming and Recursion in Python - Interview Questions and Answers

Recursion is a process where a function calls itself to solve a smaller subproblem of the original task.

def factorial(n):
    return 1 if n == 0 else n * factorial(n - 1)

The base case stops recursion, while the recursive case calls the function again with a smaller input.

By default, it's around 1000. You can check it using sys.getrecursionlimit().

import sys
sys.setrecursionlimit(2000)

A technique to solve problems by breaking them into subproblems and storing solutions to avoid redundant computation.

Recursion solves problems by calling itself. DP improves recursive solutions by storing results (memoization or tabulation).

A technique where the results of expensive function calls are cached for reuse.

A bottom-up approach that solves subproblems iteratively and stores results in a table.

from functools import lru_cache

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

When the problem has overlapping subproblems and optimal substructure.

When subproblems recur multiple times with the same input.

When an optimal solution can be built from optimal solutions of subproblems.

Because DP avoids redundant calculations through caching or bottom-up methods.

A type of recursion where the recursive call is the last thing in the function.

No, Python does not support tail call optimization to avoid stack overflows.

memo = {}
def fib(n):
    if n in memo: return memo[n]
    if n < 2: return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

Fibonacci, knapsack, coin change, LIS, LCS, matrix chain multiplication, etc.

Top-down uses recursion + memoization; bottom-up uses iteration (tabulation).

Yes, using tabulation.

def fib(n):
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

def knapsack(wt, val, W, n, memo={}):
    if n == 0 or W == 0:
        return 0
    if (n, W) in memo:
        return memo[(n, W)]
    if wt[n-1] <= W:
        memo[(n, W)] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),
                            knapsack(wt, val, W, n-1))
    else:
        memo[(n, W)] = knapsack(wt, val, W, n-1)
    return memo[(n, W)]

It finds the length of the longest sequence that appears in both strings in the same order but not necessarily contiguously.

O(m × n), where m and n are string lengths.

It depends on the number of states stored. Often O(n), O(n^2), or O(n*m).

Find the minimum number of coins to make a certain amount.

def coinChange(coins, amount):
    dp = [float('inf')] * (amount+1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount+1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

A DP problem that finds the optimal way to parenthesize matrices to minimize multiplication cost.

Tree recursion problems where subproblems are solved multiple times.

Tree traversals, backtracking, mathematical computations, DP.

A visual representation of recursive function calls.

Use print statements or logging to trace each call; add base case checks.

A classic recursive puzzle that involves moving disks between pegs under certain rules.

Missing base cases, causing infinite recursion.

Finding the longest subsequence of increasing numbers.

Using binary search with a list of potential subsequence ends.

Python uses the call stack to track recursive function calls.

Problems where all subproblems can be solved iteratively without recursion.

Efficiency – avoids recomputing subproblems.

DP checks all options for optimality, greedy chooses local optimum assuming global optimum.

Yes, with constraints – tabulation is preferred for predictability.

Yes, but you need to memoize using instance variables or decorators.

A DP technique used for solving problems on the digits of numbers, especially in number theory.

Use multidimensional lists (e.g., dp[i][j]) or dictionaries for sparse data.

def isSubsetSum(arr, n, sum):
    if sum == 0: return True
    if n == 0: return False
    if arr[n-1] > sum:
        return isSubsetSum(arr, n-1, sum)
    return isSubsetSum(arr, n-1, sum) or isSubsetSum(arr, n-1, sum - arr[n-1])

Use memoization or convert to bottom-up approach.

A technique to encode states using bitmasks, often used in combinatorial problems.

Reducing the number of dimensions by encoding multiple states into one (e.g., using bitmask).

Yes, in DFS (Depth First Search).

Backtracking uses recursion to explore all potential solutions.

Not always, but recursion has overhead due to call stack.

Yes, functools.lru_cache helps memoize recursive calls.

A classic NP-hard problem solvable by DP + bitmask.

A decorator that caches the results of function calls.

Yes, like edit distance, palindrome partitioning, LCS, etc.

Usually when n == 0, n == 1, or when constraints are violated.

Use DFS-style recursive traversal; post-order often used in DP.

def binary_search(arr, low, high, x):
    if low > high: return -1
    mid = (low + high) // 2
    if arr[mid] == x:
        return mid
    elif arr[mid] < x:
        return binary_search(arr, mid+1, high, x)
    else:
        return binary_search(arr, low, mid-1, x)

In theory, yes – but not easily in Python due to the GIL (Global Interpreter Lock).

Finding the minimum number of operations to convert one string into another.

Bottom-up solves from smallest to largest subproblems. Top-down solves recursively from the main problem.

Through the call stack; excessive depth leads to RecursionError.

A recursive approach to build solutions step-by-step and backtrack if constraints are violated.

from collections import defaultdict
memo = defaultdict(int)

Use post-order traversal to calculate DP values from children to parent.

A classic problem where we cache the minimum number of cuts needed to partition a string into palindromes.

DP uses overlapping subproblems, while D&C splits into independent subproblems.

Not always efficiently – some are better suited for iterative DP.

For very deep or time-critical tasks, due to performance and stack limits.

Python Tutor, print statements, debuggers, custom tree visualization.