6.1 辗转相减法
辗转相减法，也叫更相减损术，是出自《九章算术》中的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》中记载：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。”
翻译成现代语言如下：
第一步：任意给定两个正整数，判断它们是否都是偶数。若是，则用2约简；若不是，则执行第二步。
第二步：用较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。
我们看看下面的一个实例：
例1 用更相减损术求260和104的最大公约数。
解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。
此时65是奇数而26不是奇数，故把65和26辗转相减：
65-26=39
39-26=13
26-13=13
所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13×2×2=52。
这个过程可以简单地写为
（260，104）（/2/2）=>（65，26）=（39，26）=（13，26）=（13，13）=13.13×4=52
辗转相减法即通过对两数的不断减法运算来代替除法运算。
例如：两个自然数35和14，用大数减去小数，（35，14）=（21，14）=（7，14），此时，7小于14，要做一次交换，把14作为被减数，即（14，7）=（7，7），再做一次相减，结果为0，这样也就求出了最大公约数7。下面的代码和更相减损术的代码略有差异，省掉了以2取的过程。但本质是一样的。
Python代码如下：
这个代码中，出现了两个新的语法现象：
（1）“if（a==b）：”，这是Python中的条件判断语句，其语法是：
条件判断，可以是一切会产生True或False的运算，典型的如表6-2所示。
表6-2 条件判断语句中的运算符
（2）“def gcd2（a，b）：”，这是Python语言中函数的定义，其语法是：
def告诉Python解释器，我们定义了一个函数，它的名字就是后面跟的函数名name，这个函数有0个或以上的参数，函数内的代码块需要缩进，代码块中往往会包含一条return语句，return语句可以出现在函数体中的任何地方，它表示函数调用的结束，并将结果返回到函数调用处；return语句也不是必需的，如果它没有出现，那么函数会在执行完最后一句语句时结束。
什么情况下会需要定义一个函数呢？
函数主要有两个好处，定义好以后，可以在需要的地方反复使用，因此：
（1）最大化代码重用。
（2）把某个独立的过程用函数封装起来后，使得代码简洁，利于维护。
Python函数还有一个不同于其他语言定义的函数特征：在函数定义时，并没有规定输入和输出参数是什么类型，可以是任何参数。比如：
def addTwoElements（a,b）:
returna+b
输入参数a，b没有规定一定是数字还是字符串，或是其他的对象，所以这个函数的功能会随着输入参数的类型变化而行为有差别，如果是addTwoElements（3，5），则返回结果是8；而如果是addTwoElements（“hello”，“world”），则返回的是“helloworld”，这种随输入类型不同而不同的行为叫多态（是否像变色龙？），即多种形态的意思。
大家是否注意到上面这个函数还有一个不同寻常的地方，就是gcd2（）这个函数自己又调用了自己。这种行为是合法的，而且有个专门术语叫“递归函数”，我们举一个生活中类似的例子来理解这种函数行为，以及这种函数特有的一些约束。如果手表坏了，我们打算自己动手拆开进行维修，为了保证拆了以后能够又完整地拼装起来，我们可能会拆到某个部件时，把它和周围的部件应该如何拼接的步骤用照片或本子记下来，然后单独拿到一个新的区域去另外拆分，零件各放在独立的区域，继续拆，碰到又一个部件时，继续同样的步骤，部件和部件之间拆下来的零件不会交叉，以免混在一起。这样一直拆，拆到我们的工作区域都占满了以后，我们就会停下来，因为再拆下去，零件就会混杂在一起，再也装不回去了。递归函数也有类似的限制，每一次递归，Python都要保存一下当前的现场，即函数内变量的状态，将来函数调用返回时，我们可以继续在上次调用的地方返回去，所以不能无限制地递归下去，递归到一定程度，如果还没完成计算，就会出错，拒绝继续递归。