Python-Recursion-New To Programming

1. Your function is not recursive because it never calls itself; a recursive version would look like

   def all_positive(lst):
       if lst:
           return lst[0] > 0 and all_positive(lst[1:])
           #                       ^
           #             this is the recursive bit -
           #             the function calls itself
       else:
           return True
           #      this keeps the function from looping forever -
           #      when it runs out of list items, it stops calling itself
   

2. This is a bad example to choose for a recursive function because (a) there is a simple non-recursive solution and (b) passing it a large list (ie over 1000 items) will overflow the call stack and crash your program. Instead, try:

   def all_positive(lst):
       return all(i > 0 for i in lst)
   

With this sort of recursive problem, here is how you should think about it:

• There should be a "basis case", which answers the question trivially.

• There should be a part that does something that brings you closer to a solution.

In this case, the "basis case" will be an empty list. If the list is empty, then return True.

The part that brings you closer to a solution: shorten the list. Once the list get shortened all the way to a zero-length (empty) list, you have reached the basis case.

In pseudocode:

define function all_positive(lst)
    # basis case
    if lst is zero-length:
        return True

    if the first item in the list is not positive:
        return False

    # the actual recursive call
    return all_positive(lst[with_first_value_removed]

Try to convert the above pseudocode into Python code and get it working. When you are ready to peek at my answer, it's below.

def all_positive(lst):
    """
    Recursive function to find out if all members of lst are positive.

    Because it is recursive, it must only be used with short lists.
    """
    # basis case
    if len(lst) == 0:
        return True

    if lst[0] <= 0:
        return False

    # recursive call
    return all_positive(lst[1:])

There's several ways you can write this. One way would be to use lst.pop() to remove one element from the list. You could combine that with the if statement and it would be kind of elegant. Then the list would already be shortened and you could just do the recursive call with the list.

    if lst.pop() <= 0:
        return False

    return all_positive(lst)

There is one problem though: this destroys the list! Unless the caller knows that it destroys the list, and the caller makes a copy of the list, this is destructive. It's just plain dangerous. It's safer to do it the way I wrote it above, where you use "list slicing" to make a copy of the list that leaves off the first item.

Usually in a language like Python, we want the safer program, so we make copies of things rather than destructively changing them ("mutating" them, as we say).

Here's one more version of all_positive() that makes a single copy of the list and then destroys that copy as it works. It relies on a helper function; the helper is destructive. We don't expect the user to call the helper function directly so it has a name that starts with an underscore.

def _all_positive_helper(lst):
    """
    Recursive function that returns True if all values in a list are positive.

    Don't call this directly as it destroys its argument; call all_positive() instead.
    """
    if len(lst) == 0:
        return True

    if lst.pop() <= 0:
        return False

    return _all_positive_helper(lst)

def all_positive(lst):
    """
    Return True if all members of lst are positive; False otherwise.
    """
    # use "list slicing" to make a copy of the list
    lst_copy = lst[:]

    # the copy will be destroyed by the helper but we don't care!
    return _all_positive_helper(lst_copy) 

It's actually possible in Python to use a default argument to implement the above all in one function.

def all_positive(lst, _lst_copy=None):
    """
    Return True if all members of lst are positive; False otherwise.
    """
    if _lst_copy is None:
        return all_positive(lst, lst[:])

    if len(_lst_copy) == 0:
        return True

    if _lst_copy.pop() <= 0:
        return False

    return all_positive(lst, _lst_copy)

Recursion doesn't really help you with this. A better use for recursion would be, for example, visiting every node in a binary tree.