@extends('template')

@section('title')
    Lab 12: Fruitful recursion
@stop

@section('content')

# The "Use-it-or-lose-it" recursive problem-solving strategy

One approach for solving some advanced recursion problems is called the
"use-it-or-lose-it" approach, and it comes in handy whenever you have to
make decisions about a number of different items that can be combined in
different ways. For example, consider the following problem statement:

Write a function called `bestProductUnder` that receives two parameters:
a list of numbers and a target number. The function should return the
largest number less than or equal to the target number which can be
created as the product of one or more of the numbers in the list. It
should return None if all of the numbers in the list are greater than the
target number, or if the list is empty.

This is a challenging problem even for a human to solve, since there are
exponentially many possible ways to choose numbers to multiply together,
and unless you find a combination that exactly matches the target value
(in which case that's definitely the answer) any result you think is good
might turn out to be beaten by some other combination of numbers that's
better. Briefly consider the following call:

`bestProductUnder([13, 2, 7, 8, 3, 6, 2], 30)`

Given the numbers in the list, we could make 13×2 = 26, or 8×3 = 24, or
6×2×2 = 24, or 7×2×2 = 28, or...

As humans, we can see that 29 isn't possible (it's prime and not in our
list) and 30 isn't either, because it would need a multiple of 5 to be
present, so 28 must be the answer, but if the target number got bigger
and our list of numbers got longer, we'd start to struggle.

However, problems like this one can be solved recursively using a simple
principle of choice:

*Consider the first number in the list—it's either part of the best
solution or not.*

- If the first number is part of the best solution, then that solution is
    going to be the first number, multiplied by the solution to the
    `bestProductUnder` problem for all of the other numbers in the list,
    with a target value that's divided by the first number.
- On the other hand, if the first number isn't part of the best solution,
    then the best solution is simply the `bestProductUnder` value for the
    same target number ignoring the first number.

We can use recursion to compute these two results (each of which works
with a smaller list of numbers) and then compare them to decide which one
to return. This is called "use-it-or-lose-it" because we just look at the
first thing we have to consider, and make a choice to "use it" as part of
the solution, or to "lose it" and find a solution without it. Of course,
we actually have the computer make both choices, and then see what result
we like better.

To apply this strategy to this problem, we'll split the list of numbers
up into the first number and all of the other numbers, like this:

```py
first = nums[0]
rest = nums[1:]
```

Then we'll make two recursive calls:

```py
# Best result that uses the first number
bestWith = first * bestProductUnder(rest, target / first)

# Best result that doesn't use the first number
bestWithout = bestProductUnder(rest, target)
```

Of course, since the function can return `None` in some circumstances,
we'll have to complicate the first call:


```py
# Best result that uses the first number
bestWith = bestProductUnder(rest, target / first)

if bestWith != None:
    # If recursive result wasn't None, multiply by first number
    bestWith = first * bestWith
elif first <= target:
    # If recursive result is None, but this number alone is small enough,
    # use this number instead of None
    bestWith = first

# Best result that doesn't use the first number
bestWithout = bestProductUnder(rest, target)
```

Once we have these two results, we can compare them with each other, and take the bigger one (being careful to account for `None`s):


```py
# If one result is None, return the other, or if both are None,
# return None
if bestWith == None:
    return bestWithout # even if it's also None
elif bestWithout == None:
    return bestWith
else:
    # Return better result since neither is None
    return max(bestWith, bestWithout)
```

So putting that all together, we can define our full function, including
a base case, as:

```py
def bestProductUnder(nums, target):
    """
    Returns the largest number less than or equal to the target that can
    be formed by multiplying together one or more numbers from the given
    list of numbers. If the list is empty, or if none of the numbers in
    the list is less than or equal to the target, it returns None.
    """
    if len(nums) == 0:
        # Base case: no numbers in list
        return None
    else:
        # Recursive case: either use the first number, or skip it
        first = nums[0]
        rest = nums[1:]

        # Best w/ first number
        bestWith = bestProductUnder(rest, target / first)

        # If bestWith isn't None, multiply it by First
        if bestWith != None:
            bestWith = first * bestWith
        elif first <= target:
            # Otherwise, if the first number alone is small enough, use
            # that since none of the other numbers work
            bestWith = first

        # Best w/out first number
        bestWithout = bestProductUnder(rest, target)

        # If one result is None, return the other, or if both are None,
        # return None
        if bestWith == None:
            return bestWithout # even if it's also None
        elif bestWithout == None:
            return bestWith
        else:
            # Return better result since neither is None
            return max(bestWith, bestWithout)
```

The key idea which can be applied to many different circumstances where
you need to pick some values out of a larger list, but the values need to
combine in a complicated way, especially if there's some notion of a
"best" result. Once you can see that each value either is or isn't part
of the solution, use recursion to explore both possibilities (focusing on
a single value and letting recursion handle the rest), and then just pick
whichever result is better.

This approach does have its drawbacks, one of which is that for large
problems, it can need a huge amount of time and memory, since you're
simply asking the computer to explore every possible combination to find
the best one (each additional item in the list doubles the number of
function call frames that will be used). But it can solve some quite
complicated problems where even a human would have trouble.

@include('/labs/lab12/_toc')

@stop