# 破解数据科学面试，这里有最常考的三种算法

def factorial(n):
if n==0:
return 1
return n*factorial(n-1)

Factorial(n) = n*Factorial(n-1)

• 基线条件（base case）：递归停止的条件；

• 递归条件：函数调用自己并逐渐向基线条件移动。

def fib(n):
if n<=1:
return 1
return fib(n-1) + fib(n-2)

memo = {}
def fib_memo(n):
if n in memo:
return memo[n]
if n<=1:
memo[n]=1
return 1
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]

def fib_dp(n):
dp_sols = {0:1,1:1}
for i in range(2,n+1):
dp_sols[i] = dp_sols[i-1] + dp_sols[i-2]
return dp_sols[n]

# Returns index of target in nums array if present, else -1
def binary_search(nums, left, right, target):
# Base case
if right >= left:
mid = int((left + right)/2)
# If target is present at the mid, return
if nums[mid] == target:
return mid
# Target is smaller than mid search the elements in left
elif nums[mid] > target:
return binary_search(nums, left, mid-1, target)
# Target is larger than mid, search the elements in right
else:
return binary_search(nums, mid+1, right, target)
else:
# Target is not in nums
return -1
nums = [1,2,3,4,5,6,7,8,9]
print(binary_search(nums, 0, len(nums)-1,7))