TheDeveloperBlog.com
C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML
Ruby Recursion Example
Use recursion in a method that computes change for an amount of money.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.
Change: This is the recursive method. It first checks whether we have reached our goal amount. It tries to add coins and then calls itself.
Display: This method loops through the coins that were added. It then computes the total and displays it.
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.
Ruby program that uses recursive method
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)
Output: truncated
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 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.
Quote: More generally, can we write a procedure to compute the number of ways to change any given amount of money? This problem has a simple solution as a recursive procedure (SICP).
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.
© TheDeveloperBlog.com
The Dev Codes
Related Links:
- Ruby Convert Types: Arrays and Strings
- Ruby File Handling: File and IO Classes
- Ruby Regexp Match Method
- Ruby String Array Examples
- Ruby include: Array Contains Method
- Ruby Class Examples: Self, Super and Module
- Ruby DateTime Examples: require date
- Ruby 2D Array Examples
- Ruby Number Examples: Integer, Float, zero and eql
- Ruby Exception Examples: Begin and Rescue
- Top 65 Ruby Interview Questions (2021)
- Ruby on Rails Interview Questions (2021)
- Ruby String Examples (each char, each line)
- Ruby if Examples: elsif, else and unless
- Ruby Math Examples: floor, ceil, round and truncate
- Ruby Sub, gsub: Replace String
- Ruby Substring Examples
- Ruby Console: Puts, Print and stdin
- Ruby Remove Duplicates From Array
- Ruby Random Number Generator: rand, srand
- Ruby Recursion Example
- Ruby ROT13 Method
- Ruby Iterator: times, step Loops
- Ruby String Length, For Loop Over Chars
- Ruby Join Example (Convert Array to String)
- Ruby Format String Examples
- Ruby Copy Array Example
- Ruby Keywords
- Ruby Nil Value Examples: NoMethodError
- Learn Ruby Tutorial
- Ruby Method: Def, Arguments and Return Values
- Ruby Fibonacci Sequence Example
- Ruby Hash Examples
- Ruby While, Until and For Loop Examples
- Learn Ruby on Rails Tutorial
- Ruby Word Count: Split Method
- Ruby Sort Arrays (Use Block Syntax)
- Ruby Case Examples: Ranges, Strings and Regexp
- Ruby Array Examples
- Ruby Split String Examples