Python学习笔记(8)

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   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   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()