Previously, I used recursion to judge palindromes and draw Fractal figures, but this time it is the second one.
What is the Fibonacci sequence? 1 1 2 3 5 8 13... It is a sequence in which the sum of the previous two numbers is the next term. (Example) 3 in item 4 is the sum of the previous two 1s and 2s. This time I wrote a program that uses recursion to know the nth term of the Fibonacci sequence.
def fibonacci(n):
if n < 3:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
If it is one or two terms, it is one, and after that, it goes back to the previous and two terms, and then goes back one and two. It's a little confusing, If n = 5, the sum of the 4th and 3rd terms is required, so go back to the 2nd and 1st terms to find the sum. This gives 55 for n = 10 and 6765 for n = 20 (the larger the number, the longer it takes).
Recommended Posts