How to write an algorithm to solve the Fibonacci sequence in Python?

How to write an algorithm to solve the Fibonacci sequence in Python?

The Fibonacci sequence is a classic sequence, which is defined as follows: the first and second numbers are both 1, starting from the third number, each number is the sum of the first two numbers. and. That is: 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

In Python, you can use loops or recursion to write algorithms for solving the Fibonacci sequence . The specific implementation of these two methods will be introduced below.

Method 1: Use loops

The algorithm of using loops to solve the Fibonacci sequence is more intuitive. The code is as follows:

def fibonacci(n):
    if n <= 0:
        return "输入有误！"
    elif n <= 2:
        return 1
    else:
        a, b = 1, 1
        for _ in range(n-2):
            a, b = b, a + b
        return b

In the above code, by Set the initial values ​​​​a and b to 1, and use a loop to calculate the nth number of the Fibonacci sequence. In the loop, the values ​​of a and b are updated each time until the nth number is calculated. Finally, the value of the nth number is returned.

Method 2: Use recursion

The algorithm for solving the Fibonacci sequence using recursion is relatively simple. The code is as follows:

def fibonacci(n):
    if n <= 0:
        return "输入有误！"
    elif n <= 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

In the implementation of recursion, First determine whether the input n value is legal. If it is less than or equal to 0, an error message will be returned; if n is equal to 1 or 2, 1 will be returned directly; otherwise, the value of the nth number will be solved by recursively calling itself. The result is obtained by summing the values ​​of -1 and n-2 numbers.

It should be noted that the recursive method may have the problem of repeated calculations and is relatively inefficient. The performance of recursive algorithms can be optimized by using caching to avoid repeated calculations.

To sum up, we can write Python code in a loop or recursively to solve the Fibonacci sequence. Which method to choose depends on actual needs and code efficiency requirements.

The above is the detailed content of How to write an algorithm to solve the Fibonacci sequence in Python?. For more information, please follow other related articles on the PHP Chinese website!