Home
Ruby
Recursion Example
Updated Dec 24, 2024
Dot Net Perls
Recursion. A recursive method calls itself. This can continue forever, until stack space is exhausted. Ruby supports recursive methods.
Recursion example. Here we implement a method that determines all possible ways to count change for a certain amount. It does not find just one solution. It finds all solutions.
Method
Change. This program requires two initial arrays: an array of coins (which is at first empty) and an array of amounts. The "amounts" array stores the number of cents each coin is worth.
Array
Note Change() is the recursive method. It first checks whether we have reached our goal amount. It tries to add coins and then calls itself.
Next The change method loops through the coins that were added. It then computes the total and displays it.
Console
def change(coins, amounts, highest, sum, goal) # Display result if we have correct change. if sum == goal display(coins, amounts) end # Return if we have too much money. if sum > goal return end # Loop over coin amounts and try adding them. amounts.each do |value| if value >= highest # Copy the coins array, add value to it. copy = Array[] copy.concat coins copy.push(value) # Recursive call: add further coins if needed. change(copy, amounts, value, sum + value, goal) end end end def display(coins, amounts) # Display all the coins. amounts.each do |amount| count = 0 coins.each do |coin| if coin == amount count += 1 end end print amount, ": ", count, "\n" end print "\n" end # Specify our starting coins and all coin amounts. coins = Array[] amounts = Array[1, 5, 10, 25, 50] # Make change for 51 cents. change(coins, amounts, 0, 0, 51)
1: 51 5: 0 10: 0 25: 0 50: 0 1: 46 5: 1 10: 0 25: 0 50: 0 1: 41 5: 2 10: 0 25: 0 50: 0 1: 41 5: 0 10: 1 25: 0 50: 0...
In change, important things happen. The coins array is copied into a "copy" array. We use the concat method for this, and then push our new value into the array.
So By copying the coins array, each recursive call does not affect other calls. This is important for correct results.
In the output, we see ways to make 51 cents. We can use 51 one-cent pieces. Or we can use 46-one cent pieces and 1 five-cent piece. If you run the program, the output has all possibilities.
And The results are easy to verify. We simply check them all mentally and review our program logic.
A review. With this example from the Structure and Interpretation of Computer Programs, we consider a problem that is not trivial. Yet many real-world problems are much more complex.
Dot Net Perls is a collection of pages with code examples, which are updated to stay current. Programming is an art, and it can be learned from examples.
Donate to this site to help offset the costs of running the server. Sites like this will cease to exist if there is no financial support for them.
Sam Allen is passionate about computer languages, and he maintains 100% of the material available on this website. He hopes it makes the world a nicer place.
This page was last updated on Dec 24, 2024 (simplify).
Home
Changes
© 2007-2025 Sam Allen