Since Python allows nested functions, we can write code like the following:
def solve_knapsack(profits, weights, capacity):
def knapsack_recursive(profits, weights, capacity, currentIndex):
# base checks
if capacity <= 0 or currentIndex >= len(profits):
return 0
# recursive call after choosing the element at the currentIndex
# if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this
profit1 = 0
if weights[currentIndex] <= capacity:
profit1 = profits[currentIndex] + knapsack_recursive(
profits, weights, capacity - weights[currentIndex], currentIndex + 1)
# recursive call after excluding the element at the currentIndex
profit2 = knapsack_recursive(profits, weights, capacity, currentIndex + 1)
return max(profit1, profit2)
return knapsack_recursive(profits, weights, capacity, 0)
(If you're curious, this is the brute-force recursive solution for the Knapsack problem).
Notice that profits and weights are not mutated anytime in the nested function, but still they are passed to every recursive call. This is a pattern I've seen often, and makes sense for languages that do not allow nesting of functions, so everything needed by the function has to be passed in as arguments.
However, for Python though, the function knapsack_recursive has access to the arguments to solve_knapsack, so we can remove profits and weights from the formal parameters of the former, and the code would work just fine.
Is there a reason to choose one over the other?
