Ruby Program for Fibonacci Using Recursion

You can write a Ruby program for Fibonacci using recursion with def fibonacci(n); return n if n <= 1; fibonacci(n-1) + fibonacci(n-2); end which calls itself to calculate the Fibonacci number.

Examples

Input0

Output0

Input5

Output5

Input10

Output55

How to Think About It

To find the Fibonacci number at position n, check if n is 0 or 1 and return n directly. Otherwise, calculate it by adding the Fibonacci numbers at positions n-1 and n-2 using recursive calls.

Algorithm

1

Get the input number n.

2

If n is 0 or 1, return n as the Fibonacci number.

3

Otherwise, call the function recursively for n-1 and n-2.

4

Add the results of the two recursive calls.

5

Return the sum as the Fibonacci number for n.

Code

ruby

def fibonacci(n)
  return n if n <= 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

puts fibonacci(10)

Output

55

Dry Run

Let's trace fibonacci(5) through the code

1

Call fibonacci(5)

Since 5 > 1, calculate fibonacci(4) + fibonacci(3)

2

Call fibonacci(4)

Since 4 > 1, calculate fibonacci(3) + fibonacci(2)

3

Call fibonacci(3)

Since 3 > 1, calculate fibonacci(2) + fibonacci(1)

4

Call fibonacci(2)

Since 2 > 1, calculate fibonacci(1) + fibonacci(0)

5

Call fibonacci(1) and fibonacci(0)

Return 1 and 0 respectively

6

Calculate fibonacci(2)

1 + 0 = 1

7

Calculate fibonacci(3)

fibonacci(2) + fibonacci(1) = 1 + 1 = 2

8

Calculate fibonacci(4)

fibonacci(3) + fibonacci(2) = 2 + 1 = 3

9

Calculate fibonacci(5)

fibonacci(4) + fibonacci(3) = 3 + 2 = 5

Call	Result
fibonacci(1)	1
fibonacci(0)	0
fibonacci(2)	1
fibonacci(1)	1
fibonacci(3)	2
fibonacci(2)	1
fibonacci(4)	3
fibonacci(3)	2
fibonacci(5)	5

Why This Works

Step 1: Base Case

The function returns n directly when n is 0 or 1 to stop recursion and provide known Fibonacci values.

Step 2: Recursive Calls

For other values, the function calls itself twice with n-1 and n-2 to build the Fibonacci sequence from smaller problems.

Step 3: Combining Results

The results of the two recursive calls are added to get the Fibonacci number at position n.

Alternative Approaches

Iterative approach

ruby

def fibonacci_iterative(n)
  a, b = 0, 1
  n.times { a, b = b, a + b }
  a
end

puts fibonacci_iterative(10)

This uses a loop instead of recursion and is faster and uses less memory.

Memoization (caching results)

ruby

def fibonacci_memo(n, memo = {})
  return n if n <= 1
  memo[n] ||= fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
end

puts fibonacci_memo(10)

This stores results of previous calls to avoid repeated calculations, improving speed.

Complexity: O(2^n) time, O(n) space

Time Complexity

The recursive Fibonacci function calls itself twice for each non-base case, leading to exponential growth in calls, so time complexity is O(2^n).

Space Complexity

The maximum depth of the recursion stack is n, so space complexity is O(n).

Which Approach is Fastest?

The iterative method is fastest with O(n) time and O(1) space, while memoization improves recursion to O(n) time but uses extra memory.

Approach	Time	Space	Best For
Simple Recursion	O(2^n)	O(n)	Learning recursion basics
Memoization	O(n)	O(n)	Efficient recursion with caching
Iterative	O(n)	O(1)	Best performance and memory use