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

Introduction

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

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

policy

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]

answer

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.

Commentary

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 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.

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.

Illustrated

I made a diagram of this state in which the function is called repeatedly.

At the end

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