Coin change problem using recursion

The coin change problem is a classic problem in computer science and mathematics that involves finding the number of ways to make change for a given amount of money using a set of available coins. The problem can be solved using recursion, which is a programming technique that involves breaking down a problem into smaller sub-problems and solving them recursively.

We can solve this problem recursively by breaking it down into sub-problems. We start with the largest denomination coin and try to use as many of them as possible to make change for the given amount. Then we move on to the next largest denomination coin and repeat the process until we reach the smallest denomination coin.

Here's how the recursive solution works:

1. If the amount is 0, there is only one way to make change - by using no coins.
2. If the amount is less than 0 or we have no more coins to use, there are no ways to make change.
3. Otherwise, we have two options: a. Use the largest denomination coin and reduce the amount by that denomination. The number of ways to make change is then the number of ways to make change for the reduced amount using the remaining coins. b. Do not use the largest denomination coin and move on to the next denomination coin. The number of ways to make change is then the number of ways to make change for the original amount using the remaining coins.

Code Example

• C
• C++
• Java
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin
• Go

// C program for
// Coin change problem using recursion
#include <stdio.h>

int count(int coins[], int size, int n)
{
	if (n == 0)
	{
		// When n is zero
		return 1;
	}
	else if (n < 0)
	{
		// When n is less than zero means no solution possible
		return 0;
	}
	else if (size <= 0 && n >= 1)
	{
		// When size is zero and n is greater than 1
		return 0;
	}
	// Count solution using recursion
	return count(coins, size - 1, n) + 
      	   count(coins, size, n - coins[size - 1]);
}
int main(int argc, char
	const *argv[])
{
	// Assume given coins is positive number
	int coins[] = {
		7 , 1 , 5 , 2
	};
	// Get the number of coins
	int size = sizeof(coins) / sizeof(coins[0]);
	int n = 10;
	/*
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	int ans = count(coins, size, n);
	// Display possible result
	printf(" Result : %d \n", ans);
	return 0;
}

 Result : 12

// Include header file
#include <iostream>

using namespace std;
/*
    C++ program
    Coin change problem using recursion
*/
class Counting
{
	public: int count(int coins[], int size, int n)
	{
		if (n == 0)
		{
			// When n is zero
			return 1;
		}
		else if (n < 0)
		{
			// When n is less than zero means no solution possible
			return 0;
		}
		else if (size <= 0 && n >= 1)
		{
			// When size is zero and n is greater than 1
			return 0;
		}
		// Count solution using recursion
		return this->count(coins, size - 1, n) + this->count(coins, size, n - coins[size - 1]);
	}
};
int main()
{
	Counting *task = new Counting();
	// Assume given coins is positive number
	int coins[] = {
		7 , 1 , 5 , 2
	};
	// Get the number of coins
	int size = sizeof(coins) / sizeof(coins[0]);
	int n = 10;
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	int ans = task->count(coins, size, n);
	// Display possible result
	cout << " Result : " << ans << " \n";
	return 0;
}

 Result : 12

/*
    Java program
    Coin change problem using recursion
*/
public class Counting
{
	public int count(int[] coins, int size, int n)
	{
		if (n == 0)
		{
			// When n is zero
			return 1;
		}
		else if (n < 0)
		{
			// When n is less than zero means no solution possible
			return 0;
		}
		else if (size <= 0 && n >= 1)
		{
			// When size is zero and n is greater than 1
			return 0;
		}
		// Count solution using recursion
		return this.count(coins, size - 1, n) + 
          	   this.count(coins, size, n - coins[size - 1]);
	}
	public static void main(String[] args)
	{
		Counting task = new Counting();
		// Assume given coins is positive number
		int[] coins = {
			7 , 1 , 5 , 2
		};
		// Get the number of coins
		int size = coins.length;
		int n = 10;
		/*
		    [1,1,1,1,1,1,1,1,1,1]
		    [1,1,1,1,1,1,1,1,2]
		    [1,1,1,1,1,1,2,2]
		    [1,1,1,1,2,2,2]
		    [1,1,2,2,2,2]
		    [2,2,2,2,2]
		    [1,1,1,7]
		    [1,2,7]
		    [1,1,1,1,1,5]
		    [1,1,1,2,5]
		    [1,2,2,5]
		    [5,5]
		    -------------------
		    12 solution
		*/
		int ans = task.count(coins, size, n);
		// Display possible result
		System.out.print(" Result : " + ans + " \n");
	}
}

 Result : 12

// Include namespace system
using System;
/*
    Csharp program
    Coin change problem using recursion
*/
public class Counting
{
	public int count(int[] coins, int size, int n)
	{
		if (n == 0)
		{
			// When n is zero
			return 1;
		}
		else if (n < 0)
		{
			// When n is less than zero means no solution possible
			return 0;
		}
		else if (size <= 0 && n >= 1)
		{
			// When size is zero and n is greater than 1
			return 0;
		}
		// Count solution using recursion
		return this.count(coins, size - 1, n) + 
          this.count(coins, size, n - coins[size - 1]);
	}
	public static void Main(String[] args)
	{
		Counting task = new Counting();
		// Assume given coins is positive number
		int[] coins = {
			7 , 1 , 5 , 2
		};
		// Get the number of coins
		int size = coins.Length;
		int n = 10;
		/*
		    Target n : 10
		    ----------------
		    [1,1,1,1,1,1,1,1,1,1]
		    [1,1,1,1,1,1,1,1,2]
		    [1,1,1,1,1,1,2,2]
		    [1,1,1,1,2,2,2]
		    [1,1,2,2,2,2]
		    [2,2,2,2,2]
		    [1,1,1,7]
		    [1,2,7]
		    [1,1,1,1,1,5]
		    [1,1,1,2,5]
		    [1,2,2,5]
		    [5,5]
		    -------------------
		    12 solution
		*/
		int ans = task.count(coins, size, n);
		// Display possible result
		Console.Write(" Result : " + ans + " \n");
	}
}

 Result : 12

<?php
/*
    Php program
    Coin change problem using recursion
*/
class Counting
{
	public	function count($coins, $size, $n)
	{
		if ($n == 0)
		{
			// When n is zero
			return 1;
		}
		else if ($n < 0)
		{
			// When n is less than zero means no solution possible
			return 0;
		}
		else if ($size <= 0 && $n >= 1)
		{
			// When size is zero and n is greater than 1
			return 0;
		}
		// Count solution using recursion
		return $this->count($coins, $size - 1, $n) + 
          $this->count($coins, $size, $n - $coins[$size - 1]);
	}
}

function main()
{
	$task = new Counting();
	// Assume given coins is positive number
	$coins = array(7, 1, 5, 2);
	// Get the number of coins
	$size = count($coins);
	$n = 10;
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	$ans = $task->count($coins, $size, $n);
	// Display possible result
	echo(" Result : ".$ans.
		" \n");
}
main();

 Result : 12

/*
    Node JS program
    Coin change problem using recursion
*/
class Counting
{
	count(coins, size, n)
	{
		if (n == 0)
		{
			// When n is zero
			return 1;
		}
		else if (n < 0)
		{
			// When n is less than zero means no solution possible
			return 0;
		}
		else if (size <= 0 && n >= 1)
		{
			// When size is zero and n is greater than 1
			return 0;
		}
		// Count solution using recursion
		return this.count(coins, size - 1, n) + 
          this.count(coins, size, n - coins[size - 1]);
	}
}

function main()
{
	var task = new Counting();
	// Assume given coins is positive number
	var coins = [7, 1, 5, 2];
	// Get the number of coins
	var size = coins.length;
	var n = 10;
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	var ans = task.count(coins, size, n);
	// Display possible result
	process.stdout.write(" Result : " + ans + " \n");
}
main();

 Result : 12

#    Python 3 program
#    Coin change problem using recursion
class Counting :
	def count(self, coins, size, n) :
		if (n == 0) :
			#  When n is zero
			return 1
		elif (n < 0) :
			#  When n is less than zero means no solution possible
			return 0
		elif (size <= 0 and n >= 1) :
			#  When size is zero and n is greater than 1
			return 0
		
		#  Count solution using recursion
		return self.count(coins, size - 1, n) + self.count(
          coins, size, n - coins[size - 1])
	

def main() :
	task = Counting()
	#  Assume given coins is positive number
	coins = [7, 1, 5, 2]
	#  Get the number of coins
	size = len(coins)
	n = 10
	#    Target n : 10
	#    ----------------
	#    [1,1,1,1,1,1,1,1,1,1]
	#    [1,1,1,1,1,1,1,1,2]
	#    [1,1,1,1,1,1,2,2]
	#    [1,1,1,1,2,2,2]
	#    [1,1,2,2,2,2]
	#    [2,2,2,2,2]
	#    [1,1,1,7]
	#    [1,2,7]
	#    [1,1,1,1,1,5]
	#    [1,1,1,2,5]
	#    [1,2,2,5]
	#    [5,5]
	#    -------------------
	#    12 solution
	ans = task.count(coins, size, n)
	#  Display possible result
	print(" Result : ", ans ," ")

if __name__ == "__main__": main()

 Result :  12

#    Ruby program
#    Coin change problem using recursion
class Counting 
	def count(coins, size, n) 
		if (n == 0) 
			#  When n is zero
			return 1
		elsif (n < 0) 
			#  When n is less than zero means no solution possible
			return 0
		elsif (size <= 0 && n >= 1) 
			#  When size is zero and n is greater than 1
			return 0
		end

		#  Count solution using recursion
		return self.count(coins, size - 1, n) + 
          self.count(coins, size, n - coins[size - 1])
	end

end

def main() 
	task = Counting.new()
	#  Assume given coins is positive number
	coins = [7, 1, 5, 2]
	#  Get the number of coins
	size = coins.length
	n = 10
	#    Target n : 10
	#    ----------------
	#    [1,1,1,1,1,1,1,1,1,1]
	#    [1,1,1,1,1,1,1,1,2]
	#    [1,1,1,1,1,1,2,2]
	#    [1,1,1,1,2,2,2]
	#    [1,1,2,2,2,2]
	#    [2,2,2,2,2]
	#    [1,1,1,7]
	#    [1,2,7]
	#    [1,1,1,1,1,5]
	#    [1,1,1,2,5]
	#    [1,2,2,5]
	#    [5,5]
	#    -------------------
	#    12 solution
	ans = task.count(coins, size, n)
	#  Display possible result
	print(" Result : ", ans ," \n")
end

main()

 Result : 12 

/*
    Scala program
    Coin change problem using recursion
*/
class Counting()
{
	def count(coins: Array[Int], size: Int, n: Int): Int = {
		if (n == 0)
		{
			// When n is zero
			return 1;
		}
		else if (n < 0)
		{
			// When n is less than zero means no solution possible
			return 0;
		}
		else if (size <= 0 && n >= 1)
		{
			// When size is zero and n is greater than 1
			return 0;
		}
		// Count solution using recursion
		return this.count(coins, size - 1, n) + 
          this.count(coins, size, n - coins(size - 1));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Counting = new Counting();
		// Assume given coins is positive number
		var coins: Array[Int] = Array(7, 1, 5, 2);
		// Get the number of coins
		var size: Int = coins.length;
		var n: Int = 10;
		/*
		    Target n : 10
		    ----------------
		    [1,1,1,1,1,1,1,1,1,1]
		    [1,1,1,1,1,1,1,1,2]
		    [1,1,1,1,1,1,2,2]
		    [1,1,1,1,2,2,2]
		    [1,1,2,2,2,2]
		    [2,2,2,2,2]
		    [1,1,1,7]
		    [1,2,7]
		    [1,1,1,1,1,5]
		    [1,1,1,2,5]
		    [1,2,2,5]
		    [5,5]
		    -------------------
		    12 solution
		*/
		var ans: Int = task.count(coins, size, n);
		// Display possible result
		print(" Result : " + ans + " \n");
	}
}

 Result : 12

import Foundation;
/*
    Swift 4 program
    Coin change problem using recursion
*/
class Counting
{
	func count(_ coins: [Int], _ size: Int, _ n: Int) -> Int
	{
		if (n == 0)
		{
			// When n is zero
			return 1;
		}
		else if (n < 0)
		{
			// When n is less than zero means no solution possible
			return 0;
		}
		else if (size <= 0 && n >= 1)
		{
			// When size is zero and n is greater than 1
			return 0;
		}
		// Count solution using recursion
		return self.count(coins, size - 1, n) + 
          self.count(coins, size, n - coins[size - 1]);
	}
}
func main()
{
	let task: Counting = Counting();
	// Assume given coins is positive number
	let coins: [Int] = [7, 1, 5, 2];
	// Get the number of coins
	let size: Int = coins.count;
	let n: Int = 10;
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	let ans: Int = task.count(coins, size, n);
	// Display possible result
	print(" Result : ", ans ," ");
}
main();

 Result :  12

/*
    Kotlin program
    Coin change problem using recursion
*/
class Counting
{
	fun count(coins: Array < Int > , size: Int, n: Int): Int
	{
		if (n == 0)
		{
			// When n is zero
			return 1;
		}
		else if (n < 0)
		{
			// When n is less than zero means no solution possible
			return 0;
		}
		else if (size <= 0 && n >= 1)
		{
			// When size is zero and n is greater than 1
			return 0;
		}
		// Count solution using recursion
		return this.count(coins, size - 1, n) + 
          this.count(coins, size, n - coins[size - 1]);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Counting = Counting();
	// Assume given coins is positive number
	val coins: Array < Int > = arrayOf(7, 1, 5, 2);
	// Get the number of coins
	val size: Int = coins.count();
	val n: Int = 10;
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	val ans: Int = task.count(coins, size, n);
	// Display possible result
	print(" Result : " + ans + " \n");
}

 Result : 12

package main
import "fmt"
/*
    Go program
    Coin change problem using recursion
*/

func count(coins[] int, size int, n int) int {
	if n == 0 {
		// When n is zero
		return 1
	} else if n < 0 {
		// When n is less than zero means no solution possible
		return 0
	} else if size <= 0 && n >= 1 {
		// When size is zero and n is greater than 1
		return 0
	}
	// Count solution using recursion
	return count(coins, size - 1, n) + count(coins, size, n - coins[size - 1])
}
func main() {

	// Assume given coins is positive number
	var coins = [] int {
		7,
		1,
		5,
		2,
	}
	// Get the number of coins
	var size int = len(coins)
	var n int = 10
	/*
	    Target n : 10
	    ----------------
	    [1,1,1,1,1,1,1,1,1,1]
	    [1,1,1,1,1,1,1,1,2]
	    [1,1,1,1,1,1,2,2]
	    [1,1,1,1,2,2,2]
	    [1,1,2,2,2,2]
	    [2,2,2,2,2]
	    [1,1,1,7]
	    [1,2,7]
	    [1,1,1,1,1,5]
	    [1,1,1,2,5]
	    [1,2,2,5]
	    [5,5]
	    -------------------
	    12 solution
	*/
	var ans int = count(coins, size, n)
	// Display possible result
	fmt.Print(" Result : ", ans, " \n")
}

 Result : 12