def _knapsack01_recur(val, wt, wt_cap, n):
    """0-1 Knapsack Problem by naive recursion.

    Time complexity: O(2^n), where n is the number of items.
    Space complexity: O(n).
    """
    if n < 0 or wt_cap == 0:
        return 0
    
    if wt[n] > wt_cap:
        # Cannot be put.
        max_val = _knapsack01_recur(val, wt, wt_cap, n - 1)
    else:
        # Can be put: to put or not to put. 
        val_in = val[n] + _knapsack01_recur(val, wt, wt_cap - wt[n], n - 1)
        val_ex = _knapsack01_recur(val, wt, wt_cap, n - 1)
        max_val = max(val_in, val_ex)
    return max_val