recursion_breakout.rb

1.3-Recursion.rb

# To understand recursion, you first need to understand recursion.

# Now, on a serious note,

# a recursive function is one that calls itself.
# For a recursive algorithm to terminate you need a base case
# (e.g. a condition where the function does not call itself recursively)
# and you also need to make sure that you get closer to that base case in each recursive call.

# Let's look at a very simple example first:

def countdown(n)
  return if n.zero? # base case
  puts n
  countdown(n-1)    # getting closer to base case
end

countdown(5)

# 5
# 4
# 3
# 2
# 1

# One classic example of this construct is the Fibonacci sequence:

def fib(n)
  return n if (0..1).include? n
  fib(n-1) + fib(n-2) if n > 1
end

p fib(10)

# Some problems can be very elegantly expressed with recursion,
# e.g a lot of mathematical functions are described in a recursive way.

# Super Straight Up:

# Recursion is often prettier to look at vs: iteration.
# Tracking the memory allocation of a recursive algo is difficult.
# There are no cases in which recursion is a must.
  # Any Recursive method could be written with iteration.

# Recursion is important to you because it will come up in technical interviews.
# Veteran Devs will tell you that a solid understanding of recursion is one of the
# pivotal points that separate them from more JR devs on a team....