Recursive algorithm [calculate factorial]

2024-07-12

Recursive Algorithmis a programming technique widely used in computer science and mathematics that allows functions todirectorindirectlandCalling itselfTo solve the problem.Basic ideaIt is the process of breaking down a complex problem into smaller, similar sub-problems until those sub-problems are simple enough to be solved directly.

A recursive algorithm usually consists of two main parts:

Base Case: This is the termination condition for the recursive call, i.e. the simplest problem instance that can be solved directly without further recursive calls.
Recursive Case: This is the process of breaking down a problem into smaller sub-problems and solving them through recursive calls. The recursive case must ensure that each call is moving towards the base case.

Steps of the recursive algorithm:

Identify base cases: Determine which problems can be solved directly without further recursive calls.
Design recursive cases: define how to break down a large problem into smaller subproblems and how to combine the solutions to the subproblems to get a solution to the original problem.
Guaranteed recursion convergence: Ensure that recursive calls eventually reach the base case to avoid infinite recursion.

Advantages and disadvantages of recursive algorithms:

advantage：The code is concise, the logic is clear, and it is easy to understand and write.
shortcoming: May be less efficient than an iterative solution because it involves more function call overhead. Also, too deep a recursion may lead to a stack overflow error.

Recursion is used in many algorithms, such asTree traversal、Graph Search、Dynamic programming, etc.. Proper use of recursion can simplify the solution process of complex problems.

Example: Calculating factorial

def factorial(n):#自定义求n的阶乘函数
        if n==1:#判断n=1
                return 1#返回1结束
        else:#递归条件 即n!=1
                return n*factorial(n-1)#递归求阶乘

number = int(input("请输入一个正整数:"))#输入n的值
result = factorial(number)#调用阶乘函数
print("%d 的阶乘是 %d" %(number,result))#输出结果
1
2
3
4
5
6
7
8
9

insert image description here

Code Explanation

factorial Functions accept one parameter n, represents the number whose factorial is to be calculated. Factorial is expressed as n!, defined as all values less than or equal to n The product of the positive integers . For example,5! = 5 × 4 × 3 × 2 × 1 = 120。

Inside the function:

Basic situation: If n is equal to 1, the function directly returns 1. This is the termination condition of the recursion, because the factorial of 1 is defined as 1.
Recursive case: If n is not equal to 1, the function willn andfactorial(n-1) Multiply the results.factorial(n-1) is truefactorial functionThe call itself, but with the argument reduced by 1. This call continues until n Reach 1.

The key to recursion is that each recursive call moves closer to the base case, eventually reaching the base case and starting to return values. In this case, each recursive call decreases n by 1 until n reaches 1.

Notice:

Recursion can run into performance issues or stack overflow errors when working with large numbers, since each function call takes up some space on the stack. For simple math operations like factorials, there are often more efficient and memory-friendly iterative methods. However, recursion provides an elegant and easy-to-understand way to solve certain problems.

Technology Sharing