在编程的世界里，递归是一种特殊的函数调用方式，其中函数会调用自身。本文将为初学者介绍Python中递归的基本概念和应用。
在许多程序中，可能已经实现了一个函数调用另一个函数的情况。例如：
def A():
B()
在这个例子中，函数'A'调用了函数'B'。而递归的基本形式是函数调用自身。如果一个函数调用自己，那么这个函数就被称为递归函数。递归分为直接递归和间接递归两种类型。
直接递归是指函数在其体内直接调用自己，例如：
def rec():
rec()
间接递归则是指一个函数调用另一个函数，而这个被调用的函数又反过来调用原始函数，例如：
def A():
B()
def B():
A()
考虑以下代码：
def fun1():
print("Hello function 2")
fun2()
def fun2():
print("Hello function 1")
fun1()
能预测输出结果吗？没错，代码会无限打印！这是因为函数会不断地相互调用。但这是否意味着整个内存都会被用尽呢？不，Python会返回一个错误以防止这种情况发生。错误信息可能是：
RuntimeError: maximum recursion depth exceeded...
因此，在使用递归时，必须编写合理的代码，告诉编译器何时停止这个过程，这就是基础案例的作用。基础案例是一个已知结果或预定结果的案例，不需要任何递归调用。将在以下示例中更好地理解基础案例。
以下是一个使用递归计算前'n'个自然数之和的Python代码示例：
def rec(n):
if n == 1:
return 1 # 基础案例
else:
return (n + rec(n - 1))
last = int(input("请输入上限："))
s = rec(last)
print("从1到", last, "的数列之和是：", s)
上述代码的输出结果为：
请输入上限：4
从1到4的数列之和是：10
让理解代码的工作原理：在主块中，以用户输入的值调用rec函数，这里以4为例，即最初调用rec(4)。控制转移到rec()函数的代码，变量'n'被赋值为4。由于n==1为假，它转到else部分。第5行计算返回值为n+rec(n-1)，由于n=4，它变为4 + rec(3)。因此，rec再次被调用，值为3。这个过程一直持续，直到n的值减少到1，达到基础案例，并返回1。变量s得到返回的值10，然后在下一行打印数列的和。
递归定义是一个以更小版本的自身为定义的定义。考虑以下示例：
x^n = x * x * x * ... * n次
现在它可以以递归定义的形式表示为：
x^n = x * (x^(n-1)) for n > 1
x^n = x (for n=1) or 1 (for n=0)
在开始编写递归函数之前，必须知道，每个递归函数至少必须有两个案例。它们是：
Power(x, n) = 1 when n=0, or x (when n=1)
def gcd(p, q):
if q == 0:
return p
return gcd(q, p % q)