R Recursive Functions

Introduction

In this chapter, you will learn about recursive functions in R. A recursive function is a function that calls itself in order to solve a problem. Recursive functions are useful for solving problems that can be broken down into smaller, similar subproblems. Understanding how to write and use recursive functions is essential for certain types of problems, such as calculating factorials, generating Fibonacci sequences, and solving complex mathematical problems.

What is Recursion?

Recursion occurs when a function calls itself. Each recursive call should bring the problem closer to a base case, which is a condition under which the recursion stops. Without a base case, the recursion would continue indefinitely, leading to an error.

Basic Structure of a Recursive Function

recursive_function <- function(parameters) {
  if (base_case_condition) {
    return(base_case_value)
  } else {
    return(recursive_function(modified_parameters))
  }
}

Examples of Recursive Functions

Example 1: Calculating Factorial

The factorial of a number n (denoted as n!) is the product of all positive integers less than or equal to n. The factorial function can be defined recursively as:

• n! = n * (n - 1)!
• 1! = 1

Example:

# Define a recursive function to calculate factorial
factorial <- function(n) {
  if (n == 1) {
    return(1)  # Base case
  } else {
    return(n * factorial(n - 1))  # Recursive call
  }
}

# Call the function
print(factorial(5))  # Output: 120

Example 2: Generating Fibonacci Sequence

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. The sequence typically starts with 0 and 1. The Fibonacci function can be defined recursively as:

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2)

Example:

# Define a recursive function to generate Fibonacci numbers
fibonacci <- function(n) {
  if (n == 0) {
    return(0)  # Base case
  } else if (n == 1) {
    return(1)  # Base case
  } else {
    return(fibonacci(n - 1) + fibonacci(n - 2))  # Recursive call
  }
}

# Call the function
print(fibonacci(10))  # Output: 55

Example 3: Sum of Natural Numbers

The sum of the first n natural numbers can be calculated recursively as:

• sum(0) = 0
• sum(n) = n + sum(n - 1)

Example:

# Define a recursive function to calculate the sum of natural numbers
sum_natural_numbers <- function(n) {
  if (n == 0) {
    return(0)  # Base case
  } else {
    return(n + sum_natural_numbers(n - 1))  # Recursive call
  }
}

# Call the function
print(sum_natural_numbers(10))  # Output: 55

Handling Recursive Functions with Memoization

Recursive functions can be inefficient for problems like the Fibonacci sequence because they may repeat calculations. Memoization is a technique to store the results of expensive function calls and reuse them when the same inputs occur again.

Example 4: Fibonacci Sequence with Memoization

Example:

# Define a memoized recursive function to generate Fibonacci numbers
fibonacci_memo <- function(n, memo = c()) {
  if (!is.null(memo[n])) {
    return(memo[n])
  }
  if (n == 0) {
    result <- 0  # Base case
  } else if (n == 1) {
    result <- 1  # Base case
  } else {
    result <- fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)  # Recursive call
  }
  memo[n] <- result
  return(result)
}

# Call the function
print(fibonacci_memo(10))  # Output: 55

Example Program Using Recursive Functions

Here is an example program that demonstrates the use of recursive functions in R:

# R Program to Demonstrate Recursive Functions

# Recursive function to calculate factorial
factorial <- function(n) {
  if (n == 1) {
    return(1)  # Base case
  } else {
    return(n * factorial(n - 1))  # Recursive call
  }
}

# Recursive function to generate Fibonacci numbers
fibonacci <- function(n) {
  if (n == 0) {
    return(0)  # Base case
  } else if (n == 1) {
    return(1)  # Base case
  } else {
    return(fibonacci(n - 1) + fibonacci(n - 2))  # Recursive call
  }
}

# Recursive function to calculate the sum of natural numbers
sum_natural_numbers <- function(n) {
  if (n == 0) {
    return(0)  # Base case
  } else {
    return(n + sum_natural_numbers(n - 1))  # Recursive call
  }
}

# Call the functions
print(paste("Factorial of 5:", factorial(5)))  # Output: "Factorial of 5: 120"
print(paste("Fibonacci of 10:", fibonacci(10)))  # Output: "Fibonacci of 10: 55"
print(paste("Sum of first 10 natural numbers:", sum_natural_numbers(10)))  # Output: "Sum of first 10 natural numbers: 55"

Conclusion

In this chapter, you learned about recursive functions in R, including how to write and use them for tasks such as calculating factorials, generating Fibonacci sequences, and summing natural numbers. You also learned about memoization to optimize recursive functions. By mastering recursive functions, you can solve complex problems by breaking them down into simpler, manageable subproblems.