[재귀 곱셈 C++]

* 연산자를 사용하지 않고 양의 정수 두개를 곱하는 재귀함수를 작성하라.

덧셈, 뺄셈, 비트 시프팅 연산자를 사용할 수 있지만 사용 횟수를 최소화 해야한다.

 

#include <iostream>
using namespace std;
int minProductHelper(int smaller, int bigger)
{
	if (smaller == 0)
	{
		return 0;
	}
	else if (smaller == 1)
	{
		return bigger;
	}

	//절반 나누기 비트연산자
	int s = smaller >> 1;

	//곱절
	int halfProd = minProductHelper(s, bigger);

	if (smaller % 2 == 0)
	{
		return halfProd + halfProd;
	}
	else
	{
		return halfProd + halfProd + bigger;
	}
}
int minProduct(int a, int b)
{
	int bigger = a < b ? b : a;
	int smaller = a < b ? a : b;
	return minProductHelper(smaller, bigger);
}


int main() {
	int n;
	n = minProduct(15, 50);

	cout << n << endl;
	return 0;
}