method_recursion.rb

# Method recursion
# Recursion is a programming technique where a method calls itself in order to solve a problem.
# A recursive method typically has two main components: a base case that stops the recursion, and a recursive case that breaks the problem into smaller subproblems and calls itself.

def factorial(n)
  return 1 if n <= 1  # Base case: factorial of 0 or 1 is 1
  n * factorial(n - 1)  # Recursive case: n! = n * (n - 1)!
end

puts factorial(5)  # Output: 120 (5! = 5 * 4 * 3 * 2 * 1)
puts factorial(0)  # Output: 1 (0! = 1)
puts factorial(1)  # Output: 1 (1! = 1)

# In this example, the `factorial` method calls itself with a smaller value of `n` until it reaches the base case. This allows it to compute the factorial of any non-negative integer.

def fibonacci(n)
  return n if n <= 1  # Base case: fibonacci of 0 is 0, and fibonacci of 1 is 1
  fibonacci(n - 1) + fibonacci(n - 2)  # Recursive case: F(n) = F(n-1) + F(n-2)
end

puts fibonacci(10)  # Output: 55 (the 10th Fibonacci number)
puts fibonacci(0)   # Output: 0 (the 0th Fibonacci number)
puts fibonacci(1)   # Output: 1 (the 1st Fibonacci number)

# In this example, the `fibonacci` method calls itself twice for each value of `n` greater than 1, which can lead to a large number of function calls for larger values of `n`. This is a common issue with naive recursive implementations of the Fibonacci sequence, and it can be optimized using techniques like memoization or iterative approaches.

# Without recursion, you would need to use a loop or an iterative approach to compute the factorial or Fibonacci numbers, which can be less elegant and more verbose than the recursive solution. However, it's important to be mindful of the potential for stack overflow errors with deep recursion, especially in languages that do not optimize for tail recursion.

def without_recursion_factorial(n)
  result = 1
  (2..n).each do |i|
    result *= i
  end
  
  result
end

without_recursion_result = without_recursion_factorial(5)
puts without_recursion_result  # Output: 120 (5! = 5 * 4 * 3 * 2 * 1)