Summary of Recursion-Week 7

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.

A base case is the part of a recursive function where it doesn't call itself. Designing a recursive function requires that you carefully choose a base case and make sure that every sequence of function calls eventually reaches a base case.

example: Calculating the Sum of a List of Numbers

                      def listsum(numList):
                           if len(numList) == 1:
                              return numList[0]
                          else:
                              return numList[0] + listsum(numList[1:])

How would I compute the sum of a list of numbers? If I were a mathematician,I might start by recalling that addition is a function that is defined for two parameters, a pair of numbers. To redefine the problem from adding a list to adding pairs of numbers, I could rewrite the list as a fully parenthesized expression. Such an expression looks like this:








total= (1+(3+(5+(7+9))))total= (1+(3+(5+16)))total= (1+(3+21))total= (1+24)total= 25


listSum(numList)=first(numList)+listSum(rest(numList))

In this equation first(numList) returns the first element of the list and rest(numList) returns a list of everything but the first element.

all recursive algorithms must obey three important laws:

1. A recursive algorithm must have a base case.
2. A recursive algorithm must change its state and move toward the base case.
3. A recursive algorithm must call itself, recursively.