8.5 재귀 곱셈

문제 

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

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

 

접근법

곱셈은 격자판 안의 셀의 갯수와 같다고 볼 수 있다. 

7*8은 7*8 격자판의 셀의 갯수를 세는 것과 같을 테니까 말이다.

그렇다면 셀의 갯수는 어떻게 샐 수 있을 까?

절반을 세고 이것을 곱절로 만들어 가는 과정을 재귀적으로 처리할 수 있을 것이다. 

def Solution(a, b):
    small = a if a<b else b
    big = a if a<b else b
    return minProduct(small,big)

def minProduct(small,big):
    
    if small == 0 :
        return 0
    if small == 1:
        return big

    s = small >>1
    side1 = minProduct(s, b)
    side2 = side1 if small%2==0 else minProduct(small-s, b)
    return side1 +side2

이 코드에도 minProduct가 반복적으로 호출됨을 알 수 있다.

b는 유지되고 s에 따라 달라지므로 s에 대해 cache를 설정하여 좀더 효율적으로 개선할 수있다.

def Solution(a, b):
    memo = {}
    small = a if a<b else b
    big = a if a<b else b
    return minProduct(small,big,memo)

def minProduct(small,big,memo):

    if small == 0 :
        return 0
    if small == 1:
        return big
    if small in memo:
        return memo[small]

    s = small >>1
    side1 = minProduct(s, b)
    side2 = side1 if small%2==0 else minProduct(small-s, b)
    memo[small] = side1 + side2
    return side1 +side2

 

-더 나은 해결법

현재는 짝수인 경우에는 곱절로 더하지만, 홀수인 경우에는 작은 수의 나머지 반에 대해서도 탐색을 하고 있다.

하지만 minProduct(31,35)를 보면 minProduct(15, 35), minProduct(16,35)를 호출한다. 하지만 이것은 불필요하다

31 = 15*2 + 1 이기 떄문에 31 * 35 = 2*15*35 +35 가 되고 

그말은 즉 minProduct(15,35) *2 + 35  만 해주면 된다는 것이다. 

이런식으로 처리를 한다면 

짝수인 경우에는 곱절한 값을 리턴할 것이고, 홀수인경우에는 곱절한값 + big 값을 반환할 것이다.

그러면 매 단계 재귀 호출을 하넌만하고 호출을 할때 숫자도 매우 점점 작아지고 같은 호출을 부르는 일도 없어서 효율이 좋아진다.

def Solution(a,b):
    small = a if a<b else b
    big = a if a<b else b
    return minProduct(small,big)

def minProduct(small,big):
    if small == 0:
        return 0
    if small == 1:
        return big

    s = small>>1
    side1 = minProduct(s,big)
    if small%2 ==0:
        return side1 + side1
    else :
        return side1 + side1 + big