Recursive Functions in Ruby

In Ruby, a recursive function is a function that calls itself during its execution. This technique is particularly useful for solving problems that can be broken down into smaller, similar sub-problems. Here's a brief explanation with an example in Ruby:

def factorial(n)
  # Base case: factorial of 0 is 1
  return 1 if n == 0

  # Recursive case: n! = n * (n-1)!
  return n * factorial(n - 1)
end

# Example usage:
result = factorial(5)
puts result # Output: 120

In this example, the factorial method calculates the factorial of a given number n. The base case ensures that the recursion stops when n reaches 0, returning 1. The recursive case multiplies n by the factorial of (n-1). This process continues until the base case is reached.

When using recursion, its essential to define a base case to prevent infinite recursion. Recursive functions can be an elegant way to solve certain problems, but they should be used judiciously to avoid stack overflow errors.

A simple and basic example of a recursive function as a counter from 5 to 0

def recursive(number)
  return if number < 0
  sleep(1)
  puts(number)
  recursive(number - 1)
end

recursive(5)

A more complex recursive example is finding a file with a given location. You must change the file path and filename according to your local settings.

def search(filepath, filename)
  puts("searching: "+ filepath)
  if filepath.include?(filename)
    puts("found: "+ filename + " in " + filepath)
    true
  elsif File.file? filepath
    false
  else
    for f in Dir.children(filepath)
      found = search(File.join(filepath, f), filename)
      return true if found
    end
    false
  end
end

search("/Users/currentuser/Downloads","yoda.png")

Counting Derangements in Ruby on Rails with recursive functions is a bit difficult and a top-down approach is one of the best solutions.

class CountDerangementsTopDown
  def initialize(size)
    @set_size = size
    @sub_solutions = Array.new(size + 1, -1)
  end

  def count_derangements(n = @set_size)
    if @sub_solutions[n] != -1
      @sub_solutions[n]
    elsif n == 1
      0
    elsif n == 2
      1
    else
      result = (n - 1) * (count_derangements(n - 1) + count_derangements(n - 2))
      @sub_solutions[n] = result
      result
    end
  end
end

(1..64).each do |i|
  n = CountDerangementsTopDown.new(i).count_derangements
  puts("Derangements in set size %d > %d" % [i, n])
end

# result
# Derangements in set size 1 > 0
# Derangements in set size 2 > 1
# Derangements in set size 3 > 2
# Derangements in set size 4 > 9
# Derangements in set size 5 > 44
# Derangements in set size 6 > 265
# Derangements in set size 7 > 1854
# Derangements in set size 8 > 14833
# Derangements in set size 9 > 133496
# Derangements in set size 10 > 1334961
# Derangements in set size 11 > 14684570
# Derangements in set size 12 > 176214841
# Derangements in set size 13 > 2290792932
# Derangements in set size 14 > 32071101049
# Derangements in set size 15 > 481066515734
# Derangements in set size 16 > 7697064251745
# Derangements in set size 17 > 130850092279664
# Derangements in set size 18 > 2355301661033953
# Derangements in set size 19 > 44750731559645106
# Derangements in set size 20 > 895014631192902121
# Derangements in set size 21 > 18795307255050944540
# Derangements in set size 22 > 413496759611120779881
# Derangements in set size 23 > 9510425471055777937262
# Derangements in set size 24 > 228250211305338670494289
# Derangements in set size 25 > 5706255282633466762357224
# Derangements in set size 26 > 148362637348470135821287825
# Derangements in set size 27 > 4005791208408693667174771274
# Derangements in set size 28 > 112162153835443422680893595673
# Derangements in set size 29 > 3252702461227859257745914274516
# Derangements in set size 30 > 97581073836835777732377428235481
# Derangements in set size 31 > 3025013288941909109703700275299910
# Derangements in set size 32 > 96800425246141091510518408809597121
# Derangements in set size 33 > 3194414033122656019847107490716704992
# Derangements in set size 34 > 108610077126170304674801654684367969729
# Derangements in set size 35 > 3801352699415960663618057913952878940514
# Derangements in set size 36 > 136848697178974583890250084902303641858505
# Derangements in set size 37 > 5063401795622059603939253141385234748764684
# Derangements in set size 38 > 192409268233638264949691619372638920453057993
# Derangements in set size 39 > 7503961461111892333037973155532917897669261726
# Derangements in set size 40 > 300158458444475693321518926221316715906770469041
# Derangements in set size 41 > 12306496796223503426182275975073985352177589230680
# Derangements in set size 42 > 516872865441387143899655590953107384791458747688561
# Derangements in set size 43 > 22225533213979647187685190410983617546032726150608122
# Derangements in set size 44 > 977923461415104476258148378083279172025439950626757369
# Derangements in set size 45 > 44006555763679701431616677013747562741144797778204081604
# Derangements in set size 46 > 2024301565129266265854367142632387886092660697797387753785
# Derangements in set size 47 > 95142173561075514495155255703722230646355052796477224427894
# Derangements in set size 48 > 4566824330931624695767452273778667071025042534230906772538913
# Derangements in set size 49 > 223774392215649610092605161415154686480227084177314431854406736
# Derangements in set size 50 > 11188719610782480504630258070757734324011354208865721592720336801
# Derangements in set size 51 > 570624700149906505736143161608644450524579064652151801228737176850
# Derangements in set size 52 > 29672484407795138298279444403649511427278111361911893663894333196201
# Derangements in set size 53 > 1572641673613142329808810553393424105645739902181330364186399659398652
# Derangements in set size 54 > 84922650375109685809675769883244901704869954717791839666065581607527209
# Derangements in set size 55 > 4670745770631032719532167343578469593767847509478551181633606988413996494
# Derangements in set size 56 > 261561763155337832293801371240394297250999460530798866171481991351183803665
# Derangements in set size 57 > 14909020499854256440746678160702474943306969250255535371774473507017476808904
# Derangements in set size 58 > 864723188991546873563307333320743546711804216514821051562919463407013654916433
# Derangements in set size 59 > 51018668150501265540235132665923869255996448774374442042212248341013805640069546
# Derangements in set size 60 > 3061120089030075932414107959955432155359786926462466522532734900460828338404172761
# Derangements in set size 61 > 186728325430834631877260585557281361476947002514210457874496828928110528642654538420
# Derangements in set size 62 > 11577156176711747176390156304551444411570714155881048388218803393542852775844581382041
# Derangements in set size 63 > 729360839132840072112579847186740997928954991820506048457784613793199724878208627068582
# Derangements in set size 64 > 46679093704501764615205110219951423867453119476512387101298215282764782392205352132389249

Another approach is the bottom-up technique without a recursive function.

class CountDerangementsBottomUp
  def initialize(set_size)
    @set_size = set_size
    @sub_solutions = Array.new(set_size + 1)
    (1..@set_size).each do |n|
      @sub_solutions[n] = if n == 1
        0
      elsif n == 2
        1
      else
        (n - 1) * (@sub_solutions[n - 1] + @sub_solutions[n - 2])
      end
    end
  end

  def count_derangements
    @sub_solutions[@set_size]
  end
end

(1..64).each do |i|
  n = CountDerangementsBottomUp.new(i).count_derangements
  puts("Derangements in set size %d > %d" % [i, n])
end

And finally, there is a memory-optimized version down below:

class CountDerangementsOptimized
  def initialize(set_size)
    @set_size = set_size
    @solution_n = solution_n_minues_1 = solution_n_minues_2 = 0
    (1..@set_size).each do |n|
      @solution_n = if n == 1
        0
      elsif n == 2
        1
      else
        (n - 1) * (solution_n_minues_1 + solution_n_minues_2)
      end
      solution_n_minues_2 = solution_n_minues_1
      solution_n_minues_1 = @solution_n
    end
  end

  def count_derangements
    @solution_n
  end
end

(1..64).each do |i|
  n = CountDerangementsOptimized.new(i).count_derangements
  puts("Derangements in set size %d > %d" % [i, n])
end

Thanks for reading.

#Ruby #Recursive Functions #Dynamic Programming #Algorithms #Ruby on Rails #Derangements #Count Derangements