261 递归算法1 – 大师码

< 1 min read

递归算法 #

直接或者间接调用自身的算法称为递归算法。编程中直接或间接调用函数本身的函数称为递归函数。例如以下递归函数my_print(n)的功能是逐行打印1~n，在实现该函数的过程中又调用了my_print(n)函数本身，因此该函数是递归函数。

def my_print(n):
	if n<1:
		return
	else:
		my_print(n-1)#my_print()函数的递归调用
		print(n)
my_print(5)

上述函数的递归调用执行过程如下图所示。
调用my_print(5)函数时，my_print(5)调用my_print(4)，my_print(5)函数需要my_print(4)执行完毕，才能接着向下执行(想一想为什么?)
同样my_print(4)调用my_print(3)需要my_print(3)执行完毕，才能接着向下执行,依次类推。当调用到my_print(0)时，my_print(0)函数能执行完毕返回，然后整个程序回溯执行my_print(1)，my_print(2)……my_print(5)，逐行打印1~5。

相对于上述的递归, 我们更加容易理解迭代，事实上通过一个简单的迭代也能实现上述的功能。在迭代中我们将循环变量依次变化1~5，逐行依次打印。

for i in range(1,6):
	print(i)

而递归的思路则与上述不同，首先我们先假设已经实现了函数my_print(n),它的功能就是逐行打印1~n。那么我们可以把逐行打印1~n的任务分为逐行打印1-(n-1),打印n，依次类推，直到把问题拆分到十分易于解决为止。如下图所示：