Python学习笔记(8)
一、递归
函数调用自身，即为递归函数。
例子：
def main():
message()
def message():
print 'This is a recursive function.'
message()
main()
结果：
This is a recursive function.
This is a recursive function.
......
File "C:/temp/p19.py", line 5, in message
message()
RuntimeError: maximum recursion depth exceeded
Python解释器规定了递归深度，故运行到一定深度，将报错。
例2：
def main():
message(5)
def message(times):
if(times>0):
print 'This is a recursive function.'
message(times-1)
main()
结果：
This is a recursive function.
This is a recursive function.
This is a recursive function.
This is a recursive function.
This is a recursive function.
例3：
# This program uses recursion to calculate the factorial of a number.
def main():
# Get a number from the user.
number = input('Enter a nonnegative integer:')
# Get the factorial of the number.
fact = factorial(number)
# Display the factorial.
print 'The factorial of',number,'is',fact
def factorial(num):
if num == 0:
return 1
else:
return num*factorial(num-1)
main()
结果：
Enter a nonnegative integer:6
The factorial of 6 is 720
二、直接递归和间接递归
间接递归是函数不直接调用自己，而是采用如下形式：
1）函数A调用函数B，函数B调用函数A
2）函数A调用函数B，函数B调用函数C，函数C调用函数A
......
这样的递归才是间接递归。
例：
# The program demonstrates the range_sum function.
def main():
numbers = [1,2,3,4,5,6,7,8,9]
my_sum = range_sum(numbers,2,5)
print 'The sum of items 2 through 5 is',my_sum
def range_sum(num_list,start,end):
if start>end:
return 0
else:
return num_list[start]+range_sum(num_list,start+1,end)
main()
结果：
The sum of items 2 through 5 is 18
求最大公约数的另一种算法：
def main():
num1 = input('Enter an integer:')
num2 = input('Enter another integer:')
print 'The maximum common number:', ywf(num1,num2)
def ywf(a,b):
c = 1
if a == 0:
return b
if b == 0:
return a
if a<b:
t=a; a=b; b=t
while(a != b):
if a%2 == 0 and b % 2 == 0:
a=a/2; b=b/2; c=c*2
elif a%2 == 0 and b%2 == 1:
a=a/2
elif a%2 == 1 and b%2 == 0:
b=b/2
else:
a=a-b
if a<b:
t=a; a=b; b=t
return c
main()
例：汉若塔问题
# The program simulates the Towers of Hanoi game.
def main():
# Set up some initial values.
num_discs = 3
from_peg = 1
to_peg = 3
temp_peg = 2
# Play the game.
move_discs(num_discs,from_peg,to_peg,temp_peg)
print 'All the pegs are moved!'
# The moveDiscs function displays a disc move in the
# Towers of Hanoi game.
# num: the number of discs to move.
# from_peg: the peg to move from
# to_peg: the peg to move to
# temp_peg: the temporary peg.
def move_discs(num,from_peg,to_peg,temp_peg):
if(num>0):
move_discs(num-1,from_peg,temp_peg,to_peg)
print 'Move a disc from peg',from_peg,'to peg',to_peg
move_discs(num-1,temp_peg,to_peg,from_peg)
main()
