Ruby study memo (recursive function)

Overview

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

Fibonacci sequence

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}

Implementation

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

Ruby study memo (recursive function)
Ruby study memo (conditional branching)
[Illustration] Factorial recursive function [Ruby]
[Ruby ~ Iterative processing ~] Study memo 4
Ruby memo
Ruby Study Memo (Test Driven Development)
[wip] Ruby memo
Ruby: Account editing function
ruby basic syntax memo
[Java ~ Method ~] Study memo (5)
Ruby study notes (puts)
Dot installation study memo 01
[Java ~ Array ~] Study memo 4
Play Framework Study Memo Database ①
Java Silver Study Method Memo
[Self-use memo] (Ruby) class, class instance, instance
Personal memo Progate Ruby I (2)
[Java ~ Boolean value ~] Study memo (2)
Introduction to JUnit (study memo)
Personal memo Progate Ruby I (1)
Ruby study notes (variables & functions)
ruby exercise memo I (puts)
[Illustration] Finding the sum of coins with a recursive function [Ruby]
Ruby design pattern template method pattern memo
Play Framework Study Memo Database ②Read
ruby exercise memo VI (hello class)
[Ruby on Rails] Introduced paging function
Fibonacci sequence with (memoization) recursive function
[Study session memo] Java Day Tokyo 2017
[Ruby on Rails] CSV output function
Ruby on Rails 6.0 environment construction memo
[Ruby on Rails] DM, chat function
[Rails] Comment function implementation procedure memo
[Note] [Beginner] Ruby writing memo (refactoring) 1