Recursion

gistfile1.rb

# General structure of a recursive function
def f
  if condition
    # Base case. Stops the loop
  else
    # Recursive case. Continues loop.
  end
end

# Addition implemented with normal iteration.
def add(x, y)
  r = x
  while y > 0
    r += 1
    y -= 1
  end
  return r
end

add(5, 3)


# Addition implemented with recursion.
def add(x, y)
  if y == 0
    return x
  else
    return 1 + add(x, y - 1)
  end
end

add(5, 3)
1 + add(5, 2)
1 + 1 + add(5, 1)
1 + 1 + 1 + add(5, 0)
1 + 1 + 1 + 5

# Multiplication implemented with normal iteration.
def mul(x, y)
  r = 0
  while y > 0
    r += x
    y -= 1
  end
  return r
end

puts mul(3, 4)

# Multiplication implemented with recursion.
def mul(x, y)
  if y == 0
    return 0
  elsif y == 1
    return x
  else
    return x + mul(x, y - 1)
  end
end

mul(3, 4)
3 + mul(3, 3)
3 + 3 + mul(3, 2)
3 + 3 + 3 + mul(3, 1)
3 + 3 + 3 + 3

# Fibonacci sequence implemented with recursion.
# http://en.wikipedia.org/wiki/Fibonacci_number
def fib(x)
  if x == 1
    return 1
  elsif x == 2
    return 1
  else
    return fib(x-1) + fib(x-2)
  end
end

puts fib(7)

fib(7)
fib(6) + fib(5)
fib(5) + fib(4) + fib(4) + fib(3)
fib(4) + fib(3) + fib(3) + fib(2) + fib(3) + fib(2) + fib(2) + fib(1)
fib(3) + fib(2) + fib(2) + fib(1) + fib(2) + fib(1) + 1 + fib(2) + fib(1) + 1 + 1 + 1
fib(2) + fib(1) + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

# Quicksort.
# http://en.wikipedia.org/wiki/Quicksort
# [4, 9, 1, 8, 2, 7, 3, 6, 5]
# Pick a pivot point.
# [4, 9, 1, 8, 2, 7, 3, 6, 5]
#                 ^
# Put everyone < in one list and everything >= in another list.
# [4, 1, 2, 3, 6, 5], [9, 8, 7]
# Now you have two lists. Quicksort them.