This time, I will leave a memo that I studied for iterative processing. The for statement is fine, but this time the theme is recursion because it is better to study both for and recursion. Implement the Fibonacci sequence as a practice for recursive functions
Speaking of Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ... Thus, n items were a sequence represented by the addition of (n-1) and (n-2) items. It becomes like this when written by the recurrence formula.
\begin{align}
a_n &= 0 \quad|\quad n=0\\
&= 1 \quad|\quad n=1\\
&= a_{n-2}+a_{n-1} \quad|\quad otherwise
\end{align}
def fibonacci(n)
return 0 if n==0 #Recurrence formula 1 item
return 1 if n==1 #Recurrence formula 2 items
return fib(n-2)+fib(n-1) #Recurrence formula 3 items
end
p fibonacci(8)
Recommended Posts