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.
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.
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.
SICP. This is a classic programming exercise. It is discussed in the book Structure and Interpretation of Computer Programs. It teaches us how to use recursion and brute-force algorithms.
Also With just a single loop, and no recursion, this is a much harder problem to solve. We need to branch out and test all possibilities.
Some thoughts. Many tutorials teach us how to use methods, variables, or objects. But teaching complex problem solving is harder. Solving problems is everything.
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 tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Nov 12, 2021 (edit link).