# python recursion function

#### recursion function就是函数调用自身。recursion function通常需要下面两个过程：

1. Base case: 就是不需要调用自身就能给出答案的部分，通常是递归初始的时候。比如求阶乘 $n=1$$n=0$ 的时候

2. Recursive case: 函数调用自身进行计算的部分. 比如阶乘里面 $f(n) = f(n - 1) \times n = (n - 1)! \times n$ 部分

##### 下面是几个例子，用来说明recursion怎么构造，怎么使用
    '''
第一个问题是构造pascal 三角。下一行最两边是1， 生下来的元素是上一行两两元素的和。所以这么构造：
1： 只有一行或者两行，那就是1
2： 从第三行开始，两边是1，中间是上一行从第一个元素开始，第一个元素与第二个元素的和。

Question 1. Pascal's Triangle:

1
1     1
1     2    1
1    3     3    1
1    4     6     4    1
1    5    10     10    5    1
'''

def pascal_t(n):
if n == 1:
return [1]
elif n == 2:
return [1, 1]
elif n > 2:
po = pascal_t(n - 1)
return [1] + [po[i] + po[i+1] for i in range(len(po)-1)] + [1]

print pascal_t(6)

[1, 5, 10, 10, 5, 1]

'''
Fibonacci数：第n个数是前面两个数的和

Question 2: Fibonacci numbers from Pascal Triangle
'''
def fib(n):
pass

memo = {0:0, 1:1}
def fibm(n):
if not n in memo:
memo[n] = fibm(n-1) + fibm(n-2)
return memo[n]

fibm(6)

8

'''
列出小于等于n的质数：列出从2到n的所有数，然后对i=2，删去i的2倍，3倍，等等；对i=3，做同样的事情；
最后生下来的数字既不是2的倍数，也不是3的倍数，也不是4的倍数，等等。它们就是质数

Question 3. prime numbers. The sieve of Eratosthenes to find all prime numbers up to n.
1. Create a list of integers from two to n: 2, 3, 4, ..., n
2. Start with a counter i set to 2, i.e. the first prime number
3. Starting from i+i, count up by i and remove those numbers from the list, i.e. 2*i, 3*i, 4*i ...
4. Find the first number of the list following i. This is the next prime number.
5. Set i to the number found in the previous step
6. Repeat steps 3 and 4 until i is greater than n. (As an improvement: It's enough to go to the square root of n)
7. All the numbers, which are still in the list, are prime numbers
'''
def sieve_prime_1(n):
if n == 0 or n == 1:
return []
else:
lst = range(2, n+1)                                     # step 1
for i in range(2, n):                                   # step 2
no_p = [j for j in range(i + i, n + 1, i)]          # step 3
rest = [j for j in lst if j not in no_p]            # step 3 to remove and step 4
lst = rest                                          # step 5, 6
return rest

def sieve_prime_2(n):
if n == 0 or n == 1:
return []
else:
p = range(2, n + 1)     # step 1
for i in p:
no_p = [j for i in p for j in range(i * 2, n + 1, i)]        # step 2, 3   2*i, 3*i, 4*i ...
p = [j for j in range(2, n + 1) if j not in no_p]            # step 4, 5, 6
return p

print sieve_prime_1(50)
print sieve_prime_2(50)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

'''
爬n级台阶：每次可以爬一级或者两级。总共有多少爬法。
从第n-1到第n：增加了一级台阶，把这一级台阶插到第n-1次的所有办法里面每个办法里每个位置。然后去除重复的办法。
如果n是偶数，增加一个办法：每次都爬两级

Question 4. I want to go up a flight of stairs that has n steps. I can either take 1 or 2 steps each time.
How many different ways can I go up this flight of stairs?
'''
# n=3,  s = [[1,1,1], [1,2], [2,1]]

import itertools

# de-dup the duplicated elements in the list while the elements are lists
def dedup_list(ls):
ls0 = sorted(ls)
newls = [ls0[i] for i in xrange(len(ls0)) if i == 0 or ls[i] != ls[i - 1]]
return newls

# from n-1 to n, insert '1' to all the positions in the results of step n-1
# s is the result in step n-1, it is a list of lists
# n=3,  s = [[1,1,1], [1,2], [2,1]]
def inserts(s):
newls = []
for ls0 in s:          #e.g. ls0 = [1,1,1]
for p in xrange(len(list(ls0)) + 1):
ls0p = ls0[:p] + [1] + ls0[p:]
newls.append(ls0p)
return dedup_list(newls)

def steps(n):
if n == 1:
return [[1]]
else:
s0 = steps(n - 1)
if n % 2 == 1:
return inserts(s0)
else:
return inserts(s0) + [[2] * (n / 2)]

steps(3)

[[1, 1, 1], [1, 2], [2, 1]]

'''
反序一个列表：把最后一个元素拿出来放最前面，然后反序拿出最后一个元素后剩下来的列表
'''

def reverse_iter(x):
if len(x) == 1:
return x
elif len(x) > 1:
return [x[-1]] + reverse_iter(x[:-1])

reverse_iter([1, 2, 3, 4, 5])

[5, 4, 3, 2, 1]


reference