Python【六】：函数参数与递归调用

   函数是一种弱类型的语言，其语法相较于C/C++也大大简化，在开始今天的函数部分之前，首先要回顾下Python中变量与对象的基础。Python中变量作为值的引用存在，但是与C/C++不同，变量没有类型，只 有对象才有类型，即变量类似于一个void*；对于对象来说，分为可变对象和不可变对象，不可变对象有数值、字符串、元祖；可变对象有序列和字典。对于简单的赋值b = a来说，其实是将引用a、b同时绑定到同一个对象之上，可以使用id()查看验证。函数的定义与使用会简单介绍，今天重点来讨论下Python中的函数参数传递和递归调用。好了，惯例先上代码，然后分析：

#A Basic Program for Function

def fibs(num):
    'This is used to compose Fibs-NumSeq...'
    result = [0, 1]
    for i in range(8):
        result.append(result[-2] + result[-1])
    return result
num = input("Please input a intenger for fibs()...")
assert 0 < num
print "The fibs( " + str(num) + " ) is :" , fibs(num)

print"\n****Parameter Test****\n"

a = 1
print "id(a) : ", id(a)
print "a = ", a
def ichange(x):
    x += 1
    print "id(): ", id(x)
    print "int_change(): ", x
ichange(a)
print "a = ", a

lst = [1, 2, 3, 4, 5, 6]
print "lst is : ", lst
def lchange(x):
    x[0] = 9
    print "lst_change(): ", x
lchange(lst)
print "lst is : ", lst

print "\n****Scope Test****\n"

def scope():
    global a
    a *= 2
    print "scope(): ", a
scope()
print "a = ", a

raw_input("Enter for Exit...")

-1. 第三行到第十一行代码主要是给出一个函数的使用例子，这里是计算斐波那契数列的函数fibs()。首先使用def定义一个函数，后面跟着函数名fibs以及形参num，然后使用':'进入语句块；语句块中的主要工作是初始化一个序列，然后使用迭代式得到新的项，这里的[-2]\[-1]分别表示当前数列的最后两个项；函数最后使用return返回对象，也可以返回NULL，从而使得函数仅仅作为一个操作过程使用；
-2. 第十五行到第三十二行代码主要是体现Python中函数参数的特点。当通过形参的形式向函数传递值的时候，其实传递的是变量的值，即引用值；所以当函数内部对于参数进行修改赋值等操作时，便会根据引用绑定的对象的类型体现出不同的行为。
   比如，对于数值a = 1，由于数值属于不可变类型，因此在函数ichange()内部运行x += 1时，原有的值被“抛弃”，Python为其重新分配了一个对象，并且与变量绑定，这样原先的对象'a'并没有改变，而是变量a重新绑定了新对象，其实下面说完作用域就会知道这里是在函数局部空间中重新分配的局部对象，代码中使用id()进行了验证；
   当a是一个序列时，由于序列是可变对象，因此Python不需要再为其重新分配绑定一个新对象，所以这个时候改变会体现到原有的对象上；
   当然，这样整体给人的感觉就是像C/C++：形参的改变不会影响原始变量，Python函数也是“传值”操作；
-3. 第三十五到四十行代码在验证作用域。Python中分为全局作用域和局部作用域，函数内部属于局部作用域，即便是同名变量的操作，也会因为局部作用域优于全局作用域访问不到全局变量，方法是在局部作用域中使用global标识，从而声明这是一个全局变量，并对其操作，当然这个时候要注意不要在函数参数中定义同名变量；
   程序运行如下：

   
   从上面的程序结果可以看出，当参数时数值引用时，函数内部的操作不会改变原始对象；当参数时序列等可变对象时，函数内部的操作会对原始对象进行修改；当在函数内部中使用global标识时，可以修改全局变量。

****************************************************************************************************************

   接下我们趁热打铁，来简单看看递归调用。几乎每一种语言都定义了递归调用，函数调用自身，循环往复解决问题。使用递归调用必须包含两个基本部分：
-1. 当函数直接返回时应当由基本实例（最小可能性问题），即递归的终点，最简单的状态问题是解决的；
-2. 递归实例，递归调用自身的实例，需要时要更新相关的函数参数值；
   接下来我们借用二分法的实现来实际看看函数的递归调用，继续看个代码：

#Binary Search

import random

num = input("Please input the num what U want: ")
seq = []
for i in range(50):
    seq.append(int(random.uniform(1, 100)))
print seq, '\n\n'
seq.sort()
print '\n\n', seq
high = len(seq) - 1
low = 0

def search(seq, num, low, high):
    if low == high:
        if num == seq[low]:
            print "Found it: ", num
            return num
        else:
            print "No Found!"
            return 0
    else:
        middle = (low + high) / 2
        if num > seq[middle]:
            print num, ' > ', seq[middle]
            search(seq, num, middle + 1, high)
        else:
            print num ,' <= ', seq[middle]
            search(seq, num, low, middle)

search(seq, num, low, high)

raw_input("Enter for Exit...")

-1. 代码的开始导入了模块random，这是为了使用后面的uniform()函数来生成随机的序列，为什么不适用random()函数呢？因为random()会生成0.0-1.0之间的随机浮点数，自己希望的是100以内的整数，因此使用uniform(1, 100)控制生成随机数的范围，注意这里需要使用int类型转换；
-2. 第十行到第十三行进行二分法查找的准备工作，首先二分搜索法的序列是有序的，因此使用sort()处理；其次必须标记出当前搜索目标的头和尾，这里分别使用low和high来表示头尾索引，在搜索过程中会动态更新；
-3. 第十五行到三十行是二分法搜素函数search()的定义，这里接受四个参数，首先判断最简单的情况，即只有一个元素时，头尾索引相等，直接进行数值比较即可；当序列长度不为一时，取出中间值middle（大概值，由于整数除法的特点，并不精确，可能会偏左或偏右一个），比较与num的值，若seq[middle] < num，说明num应该在后半段，更新low = middle + 1，继续调用函数；反之则位于前半段，更新high = middle，调用函数，如此递归迭代；
-4. 二分法的要点：一是要指明终止条件，即只有一个元素时返回值；二是要使用middle不断更新参数，不断调用自身；中间加了一些print语句方便我看看得更为清楚，另外，因为要比较数值大小，使用input()函数而非raw_inpu()函数。
   最后看看结果，自己坚持输入的'9'：