종만북 수열의 빠른 합 파이썬

재귀 함수의 순서에 대해 설명

책에는 c++로 쓰여 있는데 파이썬으로 코드 작성을 했다.

import sys
print('정수 n 입력')
n = int(sys.stdin.readline())
def fastSum(n):
    if n == 1:
        return 1;
    if n%2==1: #홀수일 경우
        return fastSum(n-1) + n;
    return 2*fastSum(n/2) + (n/2)*(n/2)
print(int(fastSum(n)));

맨 아래 있는 print문의 fastSum 함수가 호출된다. n=10이다.
fastSum은 fS라고 줄이겠다.
스택엔
fS(1)
fS(2)
fS(4)
fS(5)
fS(10)
이렇게 쌓여있다.
맨 위에 fS(1)은 n=1이므로 return 1이 된다.
이후 fS(2)는 2*fS(1) + 1*1 = 2 + 1 = 3
fS(4)는 2*fS(2) + 2*2 = 6 + 4 = 10
fS(5)는 fS(4) + 5 = 10 + 5 = 15
fS(10)는 2*fS(5) + 5*5 = 30 + 25 = 55

1+2+3+4+5+6+7+8+9+10 = 55이다.

이는 for문을 돌려서 합을 구하는 것보다 빠르다.
for문을 돌리면 n번 돌아가지만 위와 같이 풀면 절반의 계산만으로도 값이 나오기 때문이다.

위 코드가 나오려면...
sum = 1+2+3+4+...+n이다
이 식을 절반으로 나눠서 생각해본다. n은 짝수라고 가정.
sum = 1+2+3+...+n/2 + n/2+1 + n/2+2 + n/2+3 ... n/2+n/2
n=10이면 1+2+3+4+5 + 5+1 + 6+1 + 7+1 + 8+1 + 9+1 이라고 보면 된다.
절반 이후의 값으로 장난을 쳐보면
n/2+1 + n/2+2 ... n/2+n/2 = n/2 * n/2 + 1+2+3+...+n/2이다

n/2가 n/2개 들어있으니 n/2*n/2이고, 뒤에는 1+2+3+...n/2가 붙는다.
뒤에 붙는 1+2+3+...n/2를 보면 1+2+3+...+n과 모양이 같다. 그러므로 이를 재귀함수로 돌리면 된다.
sum(n/2) 이런 식으로!

처음에 n을 짝수로 가정했으므로 홀수인 경우 짝수로 만들고 + n (홀수)을 해준다. -> return fastSum(n/2) + n