Python Recursion

   This week we have learned the recursion in Python language, and recursion is a process of repeating subjects in a self-similar way. 

   For example, factorial(N)=N!=N * factorial(N-1)

Then we can write the following code:

def factorial(n):

    if n==0 or n==1:

        return 1

    else: 

        return (n*factorial (n-1))

print factorial(6)

Then we will get factorial(5) is 120. However, there is a maximum limit for the value of the parameter which is related with the memory of the computer. If n is greater than the limit, then there will be an error indicated. RuntimeError: maximum recursion depth exceeded.

Another example is that if we want to calculate the sum of 1,2,3,...,100. We can write the code like this:

def add(n):

   if n<=0:

      return 0

   if n > 0 :

      return n+add(n-1)

Then if we write add(100), we will get 5050 easily.

Every program of recursion always follows the same basic steps:

1) Initial algorithm.--Recursion always needs a seed value to start with.

2) Checking the correctness of the base case.

3) Using smaller or easier subproblems to re-define the answer.

4) Running the algorithm for the sybproblems.

5) Combine the results into the expression of the answer.

6) Return the results.