[Illustration] Finding the sum of coins with a recursive function [Ruby]


About Project Euler's Probem31. A recursive function beginner explained it with reference to other people's answers in the recursive function. Illustration is also shown below, so please take a look there as well.


Problem 31 "Sum of coins" In the UK, coins are pound sterling and pence p, and there are eight types of coins in circulation: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). It is possible to make £ 2 by the following method. 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p How many ways are there to make £ 2 with these coins?

Japanese version English version official


Repeat the process of taking out any one coin from coins = [1,2,5,10,20,50,100,200] until it reaches 200. It wouldn't be great if it was done by human hands, but I can't count it, so in such cases, " recursive function "!

What is a recursive function?

A function that calls itself within the function defined by def ~ end. The Fibonacci function is often treated as an introduction to recursive functions if it is famous. If you heard it for the first time, please search.

Another commentary article: [Illustration] Factorial recursive function [Ruby]


def coin_count(coins, goal, last = 0)
  if goal == 0
    return 1

  total = 0
  coins.each do |c|
    if c < last
    if goal >= c
      total += coin_count(coins, goal - c, c)


coins = [1,2,5,10,20,50,100,200]
puts coin_count(coins,200)

I was ashamed to say that I couldn't solve it by myself, so I created it based on here. I will explain this solution in Japanese.


What I want to make this time is the number 200. So set goal = 200 and the value of one coin

First, the explanation starts from within the each statement in the function.

if c < last

This is to avoid adding more than the most recent addition, last. Since 50 + 50 + 100 and 50 + 100 + 50 are the same in this problem, only the pattern that adds in ascending order should be adopted. next is the process of skipping the process after next in the block.

Next is the third if statement in a function that uses a recursive function.

if goal >= c
  total += coin_count(coins, goal - c, c)

This time, c is one of the elements ofcoins = [1,2,5,10,20,50,100,200], so 1 <= c. So the goal passed as an argument tocoin_count (coins, goal, last)will decrease towards 0 for goal --c.

If c = 50 and goal = 200, it will be as below.

Goal with recursive function-As c is repeated, the argument goal becomes
First time: 150     ※coin_count(coins, 150, 50)Call with
Second time: 100     ※coin_count(coins, 100, 50)
Third time: 50      ※coin_count(coins, 50, 50)
4th: 0       ※coin_count(coins, 0, 50)

The fourth time the function is called with coin_count (coins, 0, 50)

if goal == 0
  return 1

It will be, so finally here,

total += coin_count(coins, goal - c, c)

The coin_count function of will have a return value of 1. At that point, it finally becomes total + = 1, and 1 is added.

--When goal> 0 --When goal <0

In this case, total = 0 remains 0 and is passed to the return value. Finally, the total number of combinations is obtained as the value of total.


I made a diagram of this state in which the function is called repeatedly. projecteuler31解説.001.jpeg

At the end

Please let me know if there are any missing points, incorrect points, or clearer explanations. Thank you for reading.

Recommended Posts

[Illustration] Finding the sum of coins with a recursive function [Ruby]
A note about the seed function of Ruby on Rails
Extract a part of a string with Ruby
The story of making a game launcher with automatic loading function [Java]
Manage the version of Ruby itself with rbenv
Finding pi with the Monte Carlo method? (Ruby)
I checked the number of taxis with Ruby
Count the number of occurrences of a string in Ruby
[Ruby] How to find the sum of each digit
Ruby study memo (recursive function)
[Illustration] Finding the sum of coins with a recursive function [Ruby]
Ruby: Account editing function
[Ruby on Rails] Introduced paging function
Fibonacci sequence with (memoization) recursive function
[Ruby on Rails] CSV output function
[Ruby on Rails] Comment function implementation
[Ruby on Rails] DM, chat function
The story of making a reverse proxy with ProxyServlet
Let's implement a function to limit the number of access to the API with SpringBoot + Redis
Determine that the value is a multiple of 〇 in Ruby
A story packed with the basics of Spring Boot (solved)
Check the operation of two roles with a chat application
The nth and n + 1st characters of a Ruby string
[Ruby] How to retrieve the contents of a double hash
Explain the benefits of the State pattern with a movie rating
Install Ruby 3.0.0 Preview 1 with a combination of Homebrew and rbenv
Aiming for a basic understanding of the flow of recursive processing
Find the number of days in a month with Kotlin
Ruby study memo (recursive function)
Build a NAS with DLNA function at the speed of a second with Raspberry Pi and Docker Compose
The basics of the process of making a call with an Android app
The story of the first Rails app refactored with a self-made helper
Try to imitate the idea of a two-dimensional array with a one-dimensional array
I tried to solve the problem of "multi-stage selection" with Ruby
I want to add a browsing function with ruby on rails
I made a Ruby container image and moved the Lambda function
A story about hitting the League Of Legends API with JAVA
A story that struggled with the introduction of Web Apple Pay
A good way to make a recursive function that reverses the characters
(Ruby on Rails6) Create a function to edit the posted content
About the behavior of ruby Hash # ==
[Ruby] See the essence of ArgumentError
Fibonacci sequence with (memoization) recursive function
Programming with ruby (on the way)
A memorandum of the FizzBuzz problem
Ruby 5 or higher sum of integers
Impressions of making BlackJack-cli with Ruby
[Ruby] Display the contents of variables
Make a typing game with ruby
Make a daily build of the TOPPERS kernel with Gitlab and Docker
Let's express the result of analyzing Java bytecode with a class diagram
[Ruby] Processing with multiple colons. A class that utilizes the module namespace.
How to access Socket directly with the TCP function of Spring Integration
Email sending function with Action Mailer at the time of new registration
Iterative processing of Ruby using each method (find the sum from 1 to 10)
(Note) Get a set of dependent library jars with the help of Gradle