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 `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
next
end
```

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)
end
```

This time, `c`

is one of the elements of`coins = [1,2,5,10,20,50,100,200]`

, so` 1 <= c`

.
So the `goal`

passed as an argument to`coin_count (coins, goal, last)`

will decrease towards 0 for` goal --c`

.

If `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)
```

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.

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

Recommended Posts