Ruby Recursion Example

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.

Based on:

Ruby 2

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.

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 text: mit.edu

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.

Related Links