python n个硬币中找一个假币，且已知假币较轻，怎么用递归和非递归两种方法求

思路:假设有数组arr，里面的int值代表银币重量，下标代表第几个银币。

循环(非递归):把数组第一个值赋值给变量tmp，从第二个变量循环到最后一个，比较循环里的变量和tmp值，如果不等，就返回小数下标。

递归:用二分思想，银币分2堆(不能均分时把中间那个留出来)，取重量小的那堆继续二分。最后只剩下一个时就是所求

下面这种写法是返回下标的。也可以把硬币假设成一种数据类型，然后返回那个类型

#!/usr/bin/python
# -*- coding: utf-8 -*-

#返回最小值下标
def getMin(arr1):
   if len(arr1)==0:return -1

   tmp=arr1[0]
   index=0
   for cur in arr1:
      if tmp!=cur:
         return 0 if tmp      index+=1
   return -1

real_index=0
#返回最小值下标 递归
def getMinRecursion(arr1):
   global real_index
   n=len(arr1)
   if n==0:return -1

   if n==1:return real_index
   if n==2:return real_index if arr1[0]
   sum1=sum(arr1[0:int(n/3)])
   sum2=sum(arr1[int(n/3):int(n/3)*2])

   if sum1==sum2:
      real_index+=int(n/3)*2
      return getMinRecursion(arr1[int(n/3)*2:n+1])
   if sum1      return getMinRecursion(arr1[0:int(n/3)])
   else:
      real_index+=int(n/3)
      return getMinRecursion(arr1[int(n/3):int(n/3)*2])

arr=[1,1,1,1,1,1,0,1,1]
print("%d"%getMin(arr))
print("%d"%getMinRecursion(arr))