recursion power 정리

이게 재귀구나

하고 깨달았다.

double power(double x, int n) {
if ( n==0 )		return 1;
else if ( n%2==0 )	return power(x*x, n/2);
else			return x * power(x*x, (n-1)/2);

만약, power(3,4)라는 값이 들어간다고 생각한다면

이 함수의 재귀호출을 정리하면 다음과 같다.

1. `power(3,4)`
   - `n`이 짝수이므로: `power(3*3, 2)`로 분할
2. `power(9,2)`
   - 다시 `n`이 짝수이므로: `power(9*9, 1)`로 분할
3. `power(81,1)`
   - 이제 `n`이 홀수이므로: `81 * power(81*81, 0)`로 분할
4. `power(81*81, 0)`
   - `n`이 0이므로: 1을 반환
5. `power(81,1)`으로 돌아가서: 
   - `81 * 1` = 81을 반환
6. `power(9,2)`로 돌아가서:
   - 이미 계산된 값 81을 반환
7. 최초의 호출 `power(3,4)`로 돌아가서:
   - 마찬가지로 이미 계산된 값 81을 반환

따라서, 결과적으로 `power(3,4)`는 81을 반환

여기서 1 다음에 81을 계속 return 하는데 함수가 어떻게 return 되는지는 더 공부할 필요가 있어보인다.

"같이 스터디 하시는 분이 정리해주신 그림이다!"

끝

2023.03.31. 함수가 어떻게 구현되는지 더 궁금하다.