Fibonacci Sequence Using Recursion in R

by

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, typically starting with 0 and 1. This sequence has numerous applications in computer science, mathematics, and nature. In this comprehensive guide, we will explore how to generate the Fibonacci sequence using recursion in R. We will cover three different solutions, providing detailed explanations and outputs for each. Before diving into the examples, let’s review the prerequisites necessary for this article.

Prerequisites

To follow along with this guide, you should have:

  • Basic knowledge of R programming
  • R and RStudio installed on your machine
  • Familiarity with functions and recursion in R

1. Basic Recursive Function

1.1. Example 1: Simple Recursive Fibonacci Function

In this example, we will implement a simple recursive function to generate the Fibonacci sequence.

Code

R
# Function to generate nth Fibonacci number using recursion
fibonacci_recursive <- function(n) {
  if (n <= 1) {
    return(n)
  } else {
    return(fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2))
  }
}

# Test the function with an example
n <- 10
fibonacci_sequence <- sapply(0:(n-1), fibonacci_recursive)
cat("Fibonacci sequence up to", n, "terms:", fibonacci_sequence, "\n")

Explanation

  • Function Definition: We define a function fibonacci_recursive to generate the nth Fibonacci number using recursion.
  • Base Cases: The function checks if the number is 0 or 1 and returns the corresponding value.
  • Recursive Call: For other numbers, the function recursively calls itself with n−1n-1n−1 and n−2n-2n−2 and sums the results.
  • Testing: We test the function to generate the first 10 terms of the Fibonacci sequence and print the result.

Output

R
Fibonacci sequence up to 10 terms: 0 1 1 2 3 5 8 13 21 34

1.2. Example 2: Optimized Recursive Fibonacci with Memoization

In this example, we optimize the previous function using memoization to store and reuse previously computed values.

Code

R
# Function to generate nth Fibonacci number using recursion with memoization
fibonacci_memo <- function() {
  cache <- c(0, 1)
  f <- function(n) {
    if (n < length(cache)) {
      return(cache[n + 1])
    } else {
      result <- f(n - 1) + f(n - 2)
      cache[n + 1] <<- result
      return(result)
    }
  }
  return(f)
}

# Test the memoized function with an example
fibonacci_memoized <- fibonacci_memo()
n <- 10
fibonacci_sequence <- sapply(0:(n-1), fibonacci_memoized)
cat("Fibonacci sequence up to", n, "terms (memoized):", fibonacci_sequence, "\n")

Explanation

  • Memoization Function: We define a memoization function fibonacci_memo that returns a memoized version of the Fibonacci function.
  • Cache Storage: The function uses a cache to store previously computed Fibonacci numbers.
  • Recursive Calculation: The memoized function calculates the Fibonacci number and stores the result in the cache to avoid redundant calculations.
  • Testing: We test the memoized function to generate the first 10 terms of the Fibonacci sequence and print the result.

Output

R
Fibonacci sequence up to 10 terms (memoized): 0 1 1 2 3 5 8 13 21 34

2. Advanced Recursive Function

2.1. Example 3: Tail Recursion

In this example, we implement a tail-recursive function to generate the Fibonacci sequence, which is more efficient for larger numbers.

Code

R
# Tail-recursive function to generate nth Fibonacci number
fibonacci_tail_recursive <- function(n, a = 0, b = 1) {
  if (n == 0) {
    return(a)
  } else if (n == 1) {
    return(b)
  } else {
    return(fibonacci_tail_recursive(n - 1, b, a + b))
  }
}

# Test the tail-recursive function with an example
n <- 10
fibonacci_sequence <- sapply(0:(n-1), fibonacci_tail_recursive)
cat("Fibonacci sequence up to", n, "terms (tail-recursive):", fibonacci_sequence, "\n")

Explanation

  • Tail-Recursive Function: We define a tail-recursive function fibonacci_tail_recursive to generate the nth Fibonacci number.
  • Parameters: The function includes additional parameters a and b to hold the intermediate Fibonacci numbers.
  • Base Cases and Recursive Call: The function checks the base cases and recursively calls itself, passing the updated parameters.
  • Testing: We test the tail-recursive function to generate the first 10 terms of the Fibonacci sequence and print the result.

Output

R
Fibonacci sequence up to 10 terms (tail-recursive): 0 1 1 2 3 5 8 13 21 34

2.2. Example 4: Vectorized Fibonacci Function

In this example, we use a vectorized approach to generate the Fibonacci sequence up to nnn terms.

Code

R
# Function to generate Fibonacci sequence using vectorized operations
fibonacci_vectorized <- function(n) {
  fibonacci <- numeric(n)
  fibonacci[1] <- 0
  if (n > 1) {
    fibonacci[2] <- 1
    for (i in 3:n) {
      fibonacci[i] <- fibonacci[i - 1] + fibonacci[i - 2]
    }
  }
  return(fibonacci)
}

# Test the vectorized function with an example
n <- 10
fibonacci_sequence <- fibonacci_vectorized(n)
cat("Fibonacci sequence up to", n, "terms (vectorized):", fibonacci_sequence, "\n")

Explanation

  • Vectorized Function: We define a function fibonacci_vectorized to generate the Fibonacci sequence using vectorized operations.
  • Initialization: The function initializes a numeric vector fibonacci to hold the sequence.
  • Loop and Vectorized Operations: The function uses a loop to calculate the sequence and store the results in the vector.
  • Testing: We test the vectorized function to generate the first 10 terms of the Fibonacci sequence and print the result.

Output

R
Fibonacci sequence up to 10 terms (vectorized): 0 1 1 2 3 5 8 13 21 34

2.3. Example 5: Using dplyr for Fibonacci Sequence

The dplyr package in R provides powerful tools for data manipulation. In this example, we use dplyr to generate the Fibonacci sequence.

Code

R
# Install and load the dplyr package
install.packages("dplyr")
library(dplyr)

# Function to generate Fibonacci sequence using dplyr
fibonacci_dplyr <- function(n) {
  df <- tibble::tibble(
    n = 0:(n-1)
  ) %>%
    mutate(
      Fibonacci = case_when(
        n == 0 ~ 0,
        n == 1 ~ 1,
        TRUE ~ lag(Fibonacci, 1) + lag(Fibonacci, 2)
      )
    )
  return(df$Fibonacci)
}

# Test the dplyr function with an example
n <- 10
fibonacci_sequence <- fibonacci_dplyr(n)
cat("Fibonacci sequence up to", n, "terms (dplyr):", fibonacci_sequence, "\n")

Explanation

  • Package Installation: We install and load the dplyr package.
  • Data Frame Creation: We create a data frame df with a column of numbers from 0 to n−1n-1n−1.
  • dplyr Operations: We use mutate and case_when to calculate the Fibonacci sequence and store the results in the Fibonacci column.
  • Testing: We test the dplyr function to generate the first 10 terms of the Fibonacci sequence and print the result.

Output

R
Fibonacci sequence up to 10 terms (dplyr): 0 1 1 2 3 5 8 13 21 34

Conclusion

In this comprehensive guide, we explored various methods to generate the Fibonacci sequence using recursion in R. We demonstrated how to use simple recursion, optimize the function with memoization, and implement tail recursion for efficiency. Additionally, we used vectorized operations and the dplyr package for data manipulation and sequence generation. Each method offers a unique approach to generating the Fibonacci sequence, catering to different needs in data analysis and computational tasks. By mastering these techniques, you can efficiently handle Fibonacci sequence generation in R, enhancing your data processing and algorithm development skills.