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 "!
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 end total = 0 coins.each do |c| if c < last next end if goal >= c total += coin_count(coins, goal - c, c) end end total end 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
goal = 200 and the value of one coin
First, the explanation starts from within the each statement in the function.
if c < last next end
This is to avoid adding more than the most recent addition,
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) end
c is one of the elements of
coins = [1,2,5,10,20,50,100,200], so
1 <= c.
goal passed as an argument to
coin_count (coins, goal, last)will decrease towards 0 for
c = 50 and goal = 200, it will be as below.
Example) 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 end
It will be, so finally here,
total += coin_count(coins, goal - c, c)
coin_count function of will have a
return value of 1.
At that point, it finally becomes
total + = 1, and 1 is added.
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.
Please let me know if there are any missing points, incorrect points, or clearer explanations. Thank you for reading.