Python 中的基本递归程序

2025年3月17日 | 阅读 7 分钟

递归是编程中解决问题的一个重要概念。每个初学者都会遇到递归，即使是有经验的开发者也会使用递归。如果你不熟悉递归，它是一个函数调用自身的机制。例如 - 放置两个相对的镜子，当有物体出现在它们之间时，它会被递归地反射。要了解更多关于递归的信息，请访问 www.javatpoint.com/recursion-in-python。

在本教程中，我们将使用递归解决一些重要的 Python 问题。这将有助于加深对递归的理解以及如何着手解决问题。

让我们来看一下这些问题。

求一个数的阶乘

这是递归的一个入门级或著名问题。一个数的阶乘是通过将该数乘以 n-1 直到得到 1 来计算的。假设我们想计算 5 的阶乘，它将如下所示。

0! = 1
1! = 1x0! = 1x1 = 1
2! = 2x1! = 2
3! = 3x2! = 3x2 = 6
4! = 4x3! = 4x6 = 24
5! = 5x4! = 5x24 = 120

正如我们所看到的，它反复计算 n*(n-1)。因此，我们可以使用递归。这里 0 的阶乘是 1。递归的基线情况如下 -

if n==0 return 1
fact(n) = n * f(n-1)  n<1

代码如下。

示例 -

def factorial(n):
	    if n==0:
	        return 1
	    else:
	        return n*factorial(n-1)

num = int(input("Enter a number: "))
print("The factorial of a {0} is: ".format(num), factorial(num))

输出

Enter a number: 6
The factorial of a 6 is:  720

斐波那契数列

这是一个非常著名的数学问题，有时也会在初级职位的面试中出现。在这个数列中，数列中的每个数字都是它前面两个数字的和。该数列为 0, 1, 1, 2, 3, 5, 8, ... 等等。第一个元素是 0，第二个是 1；因此，第三个元素是第一个和第二个元素的和。假设我们想要斐波那契数列的第 6 个元素，那么它前面两个元素将是 5 和 4 -

fib(6) = fib(5) + fib(4) => 5 + 3 = 8
fib(5) = fib(4) + fib(3) => 2 +  3 = 5
fib(4) = fib(3) + fib(2) => 2 + 1 = 3
fib(3) = fib(2) + fib(1) => 1 + 1 = 2

数列 Fn 由以下递推关系定义。

以及初始值 -

让我们用 Python 代码来实现这个递推关系。

示例 -

def fib(n) :
    if n==0:
        return 0
    elif n ==1 :
        return 1
    else :
        return fib(n-1) +fib(n-2)
num = int(input("Enter a number: "))
print("The {num} element of fibonacci series is: ".format(num), fib(7))

输出

Enter a number: 7
The 7 element of fibonacci series is:  13

求前 n 个自然数的和

这是一个简单的问题，我们使用递归来求 n 个自然数的和。

示例 -

def sumnums(n):
    if n == 1:
        return 1
    return n + sumnums(n - 1)
num = int(input("Enter a number: "))print(sumnums(3))
print(sumnums(6))
print(sumnums(9))

输出

Enter a number: 6
21

求一个数的幂

求一个数的幂，需要一个底数和一个指数。将一个数乘以自身，次数等于指数的值。指数写在底数的上方和右侧。每次将底数相乘时，指数都会减一。

示例 -

def power_of_num(num, topwr):
    if topwr == 0:
        return 1
    else:
        return num * power_of_num(num, topwr - 1)

print('{} to the power of {} is: {} '.format(4, 7, power_of_num(3, 7)))
print('{} to the power of {} is: {} '.format(2, 8, power_of_num(4, 3)))

输出

4 to the power of 7 is: 2187 
2 to the power of 8 is: 64

求两个数的最小公倍数 (LCM)

在数学中，LCM 是两个或多个数字的最小公因子。例如 - 我们想找出 2 和 5 的公因子，那么 -

2 的倍数 → 2, 4, 6, 8, 10

5 的倍数 → 5, 10, 15, 20, 25

最小公倍数是 → 10

让我们看下面的例子 -

示例 -

def LCM(x, y):
  z = x % y
  if z == 0:
        return x
  return x * LCM(y, z) / z
print("The least common factor is: ", LCM(4, 16))

输出

The least common factor is:  16.0

求两个数的最大公约数 (GCD)

它也称为最大公因子 (HCF)，它是能同时整除两个给定数字的最高公因子。例如 - 假设我们要找出 a = 98 和 b = 56 的 HCF。

这里 a>b，所以我们将 a 的值减去 b，而 b 保持不变

a = a - b = 98 - 56 = 42，b = 56。现在 b>a，所以 b = b - a = 56 - 42 = 14，a = 42。42 是 14 的 3 倍，所以 HCF 是 14。

让我们用 Python 代码来实现它。

示例 -

def gcd(a,b):
	
	if (a == 0):
		return b
	if (b == 0):
		return a

	# base case of recursion
	if (a == b):
		return a

	# when a is greater
	if (a > b):
		return gcd(a-b, b)
	# when b is greater
	return gcd(a, b-a)
a = 24
b = 48
if(gcd(a, b)):
	print('GCD of', a, 'and', b, 'is', gcd(a, b))
else:
	print('not found')

输出

GCD of 24 and 48 is 24

汉诺塔

这是一个著名的数学谜题，有三根杆子和三个圆盘。主要任务是将整个堆栈移动到另一个杆子上，并且必须遵守以下规则 -

一次只能移动一个圆盘。
可以移动任意一个杆子最上面的圆盘。
小圆盘不能放在大圆盘的下面。

让我们用下面的例子来解决这个代码。

示例 -

# Creating a recursive function  
def tower_of_hanoi(disks, source, auxiliary, target):  
    if(disks == 1):  
        print('Move disk 1 from rod {} to rod {}.'.format(source, target))  
        return  
    # function call itself  
    tower_of_hanoi(disks - 1, source, target, auxiliary)  
    print('Move disk {} from rod {} to rod {}.'.format(disks, source, target))  
    tower_of_hanoi(disks - 1, auxiliary, source, target)  
  
  
disks = int(input('Enter the number of disks: '))  
# We are referring source as A, auxiliary as B, and target as C  
tower_of_hanoi(disks, 'A', 'B', 'C')  # Calling the function  

输出

Enter number of disks: 2  
Move disk 1 from rod A to rod B.  
Move disk 2 from rod A to rod C.  
Move disk 1 from rod B to rod C.

求一个数的各位数字之和

我们也可以使用递归来解决这类问题。假设用户输入 143，则数字之和为 1+4+3 = 8。让我们来理解下面的例子。

示例 -

def sumDigits(no):
    if no == 0:
        return 0
    else :
        return int(no % 10) + sumDigits(int(no / 10))
nums = int(input("Enter a number: "))
print("The sum is:", sumDigits(nums))

输出

Enter a number: 143
The sum is: 8

合并排序

归并排序算法基于分治法，是最有效的算法之一。在归并排序算法中，给定的数组被分解成多个数组，直到每个数组只包含一个元素。然后进行排序，并合并成一个单一的数组。访问我们的 Python 归并排序算法以获得详细的解释。

示例 -

def merge_sort(list1):
    length = len(list1)
    if length > 1:
        middle = length // 2
        left_arr = list1[:middle]
        right_arr = list1[middle:]

        merge_sort(left_arr)
        merge_sort(right_arr)

        p = 0
        q = 0
        r = 0

        left_length = len(left_arr)
        right_length = len(right_arr)
        while p < left_length and q < right_length:
            if left_arr[p] < right_arr[q]:
                list1[r] = left_arr[p]
                p += 1
            else:
                list1[r] = right_arr[q]
                q += 1

            r += 1

        while p < left_length:
            list1[r] = left_arr[p]
            p += 1
            r += 1

        while q < right_length:
            list1[r] = right_arr[q]
            q += 1
            r += 1

list1 = [24, 11, 50, 27, 16, 36, 60, 91]
print("Input Array: ")
print(list1)
merge_sort(list1)
print("Sorted Array :")
print(list1)

输出

Input Array: 
[24, 11, 50, 27, 16, 36, 60, 91]
Sorted Array :
[11, 16, 24, 27, 36, 50, 60, 91]

帕斯卡三角形

帕斯卡三角形是一种特殊的三角形，其中每个数字是上面两个数字的和，除了边缘上的数字，它们都是 '1'。

让我们来理解以下代码。

示例 -

def pascal(n):
    if n == 1:
        return [1]
    else:
        line = [1]
        previous_line = pascal(n-1)
        for i in range(len(previous_line)-1):
            line.append(previous_line[i] + previous_line[i+1])
        line += [1]
    return line
num = int(input("Enter a number: "))
print(pascal(num))

输出

Enter a number: 6
[1, 5, 10, 10, 5, 1]

结论

递归可以减少代码行数，但会占用更多内存。在本教程中，我们讨论了一些可以使用递归解决的简单问题。这些常见问题可能会在编程面试中出现。

下一主题如何在 Python 中设计哈希集合

Python 中的基本递归程序

求一个数的阶乘

斐波那契数列

求前 n 个自然数的和

求一个数的幂

求两个数的最小公倍数 (LCM)

求两个数的最大公约数 (GCD)

汉诺塔

求一个数的各位数字之和

合并排序

帕斯卡三角形

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

Python 中的基本递归程序

求一个数的阶乘

斐波那契数列

求前 n 个自然数的和

求一个数的幂

求两个数的最小公倍数 (LCM)

求两个数的最大公约数 (GCD)

汉诺塔

求一个数的各位数字之和

合并排序

帕斯卡三角形

结论

相关帖子

Python Property 装饰器

Python 可变与不可变数据类型

使用 Python 进行 Android 开发

Python Faker

Python Graphviz

Python 的 Configparser 模块

类方法 vs 静态方法 vs 实例方法

编写 Python 程序打印所有可能的整数组合

Java 开发人员的 Python 基础

Python 中的 IDLE 软件

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器