How do you print a Fibonacci sequence using recursion?

Printing a Fibonacci sequence using recursion is a classic problem that helps illustrate the power and potential pitfalls of recursive algorithms. Let’s break down the concept, provide an example, and show how to implement it in different programming languages.

Understanding the Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. The sequence goes:

[ 0, 1, 1, 2, 3, 5, 8, 13, \ldots ]

Recursive Definition

To find the Fibonacci number at position ( n ) (denoted as ( F(n) )), we use the following recursive definition:

• ( F(0) = 0 )
• ( F(1) = 1 )
• For ( n \geq 2 ): ( F(n) = F(n-1) + F(n-2) )

Recursive Approach

1. Base Case: Define the Fibonacci numbers for ( n = 0 ) and ( n = 1 ) directly.
2. Recursive Case: For ( n \geq 2 ), compute ( F(n) ) as ( F(n-1) + F(n-2) ), and call the function recursively for ( n-1 ) and ( n-2 ).

Example Walkthrough

To print the first 5 numbers of the Fibonacci sequence:

1. Start with ( n = 5 ).
2. Compute ( F(5) ):

• ( F(5) = F(4) + F(3) )
• Compute ( F(4) ):
  • ( F(4) = F(3) + F(2) )
  • Compute ( F(3) ):
  • ( F(3) = F(2) + F(1) )
  • Compute ( F(2) ):
    • ( F(2) = F(1) + F(0) )
    • Base cases: ( F(1) = 1 ), ( F(0) = 0 )
  • Combine results: ( F(2) = 1 + 0 = 1 )
  • Combine results: ( F(3) = 1 + 1 = 2 )
• Combine results: ( F(4) = 2 + 1 = 3 )
• Combine results: ( F(5) = 3 + 2 = 5 )

Printing the Fibonacci Sequence Using Recursion

To print the Fibonacci sequence up to the nth number, you would typically use a recursive function that prints each Fibonacci number up to the desired index.

Code Examples

1. Python

def fibonacci(n):
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    elif n == 2:
        return [0, 1]
    else:
        seq = fibonacci(n - 1)
        seq.append(seq[-1] + seq[-2])
        return seq

# Example usage
n = 5
print("Fibonacci sequence up to", n, "numbers:", fibonacci(n))

2. JavaScript

function fibonacci(n) {
    if (n <= 0) {
        return [];
    } else if (n === 1) {
        return [0];
    } else if (n === 2) {
        return [0, 1];
    } else {
        let seq = fibonacci(n - 1);
        seq.push(seq[seq.length - 1] + seq[seq.length - 2]);
        return seq;
    }
}

// Example usage
const n = 5;
console.log("Fibonacci sequence up to", n, "numbers:", fibonacci(n));

3. Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static List<Integer> fibonacci(int n) {
        List<Integer> seq = new ArrayList<>();
        if (n <= 0) return seq;
        if (n == 1) {
            seq.add(0);
            return seq;
        }
        if (n == 2) {
            seq.add(0);
            seq.add(1);
            return seq;
        }
        seq = fibonacci(n - 1);
        seq.add(seq.get(seq.size() - 1) + seq.get(seq.size() - 2));
        return seq;
    }

    public static void main(String[] args) {
        int n = 5;
        List<Integer> sequence = fibonacci(n);
        System.out.println("Fibonacci sequence up to " + n + " numbers: " + sequence);
    }
}

4. C++

#include <iostream>
#include <vector>

std::vector<int> fibonacci(int n) {
    std::vector<int> seq;
    if (n <= 0) return seq;
    if (n == 1) {
        seq.push_back(0);
        return seq;
    }
    if (n == 2) {
        seq.push_back(0);
        seq.push_back(1);
        return seq;
    }
    seq = fibonacci(n - 1);
    seq.push_back(seq[seq.size() - 1] + seq[seq.size() - 2]);
    return seq;
}

int main() {
    int n = 5;
    std::vector<int> sequence = fibonacci(n);
    std::cout << "Fibonacci sequence up to " << n << " numbers: ";
    for (int num : sequence) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

5. C

using System;
using System.Collections.Generic;

class Program {
    public static List<int> Fibonacci(int n) {
        List<int> seq = new List<int>();
        if (n <= 0) return seq;
        if (n == 1) {
            seq.Add(0);
            return seq;
        }
        if (n == 2) {
            seq.Add(0);
            seq.Add(1);
            return seq;
        }
        seq = Fibonacci(n - 1);
        seq.Add(seq[seq.Count - 1] + seq[seq.Count - 2]);
        return seq;
    }

    static void Main() {
        int n = 5;
        List<int> sequence = Fibonacci(n);
        Console.Write("Fibonacci sequence up to " + n + " numbers: ");
        foreach (int num in sequence) {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}

To print a Fibonacci sequence using recursion, you define a recursive function that builds the sequence up to the desired length by combining the results of smaller subproblems. The provided code examples in Python, JavaScript, Java, C++, and C# demonstrate how to accomplish this in various languages. Each example builds the Fibonacci sequence by leveraging recursion to compute the sequence elements step-by-step.