정보처리기사 [프로그래밍 언어 활용]

C언어

재귀함수

1. 다음 함수 fib()를 사용하여 fib(5)를 실행했을 때 fib(5)를 포함한 fib() 함수의 총 호출 횟수와 최종 리턴 값을 순서대로 쓰시오.

int fib(int n)
{
    if(n <= 0) return 0;
      if(n == 1) return 1;
      else return (fib(n-1) + fib(n-2));
}

기본 개념 정리

1. 호출 횟수는 함수가 실행되는 횟수를 의미합니다.

   • 예를 들어, fib(5)가 실행되면 1번 호출되고, 그 안에서 또 다른 함수들이 실행되면서 호출 횟수가 증가합니다.

2. 중복 호출은 같은 함수가 여러 번 호출되는 것을 의미합니다. 재귀 함수에서 동일한 함수가 여러 번 호출되기 때문에, 중복 호출이 발생합니다. 예를 들어, fib(3)이 두 번 호출되면 fib(3)의 호출 횟수는 2번이 됩니다.

   중복 호출을 포함한 fib(5) 실행 흐름

   1. fib(5) 호출:

• fib(5)가 실행되면, 내부에서 fib(4)와 fib(3)을 호출합니다.

  • 호출 횟수: 1번 (함수 fib(5)가 실행됨)
  • 그 안에서 fib(4)와 fib(3)이 호출되므로 2번 호출이 발생합니다.

  2. fib(4) 호출:

• fib(4)가 실행되면, 내부에서 fib(3)과 fib(2)를 호출합니다.

  • 호출 횟수: 1번 (fib(4) 실행)
  • 그 안에서 fib(3)와 fib(2)가 호출되므로 2번 호출이 발생합니다.

  3. fib(3) 호출 (첫 번째):

• fib(3)가 실행되면, 내부에서 fib(2)와 fib(1)을 호출합니다.

  • 호출 횟수: 1번 (fib(3) 실행)
  • 그 안에서 fib(2)와 fib(1)이 호출되므로 2번 호출이 발생합니다.

  4. fib(2) 호출 (첫 번째):

• fib(2)가 실행되면, 내부에서 fib(1)과 fib(0)을 호출합니다.

  • 호출 횟수: 1번 (fib(2) 실행)
  • 그 안에서 fib(1)과 fib(0)이 호출되므로 2번 호출이 발생します.

  5. fib(1) 호출 (첫 번째):

• fib(1)이 실행되면, 1을 리턴합니다.

  • 호출 횟수: 1번 (fib(1) 실행)

  6. fib(0) 호출 (첫 번째):

• fib(0)이 실행되면, 0을 리턴합니다.

  • 호출 횟수: 1번 (fib(0) 실행)

  7. fib(2) 리턴 후, fib(3)에서 fib(1)과 fib(0)을 호출:

• fib(3)이 실행되면서, 다시 fib(1)과 fib(0)이 호출됩니다.

  • 호출 횟수: 2번 (fib(1)과 fib(0) 호출)

  8. fib(3) 리턴 후, fib(4)에서 fib(3)과 fib(2)를 호출:

• fib(4)가 실행되면, fib(3)과 fib(2)가 호출됩니다.

  • fib(3)이 이미 리턴된 값을 사용하고,
  • fib(2)도 이미 리턴된 값을 사용합니다.
  • 호출 횟수: 2번 (fib(3)과 fib(2) 호출)

  9. fib(4) 리턴 후, fib(5)에서 fib(4)와 fib(3)을 호출:

• fib(5)가 실행되면서, fib(4)와 fib(3)을 호출합니다.

  • 호출 횟수: 2번 (fib(4)와 fib(3) 호출)

  중복 호출이 일어나는 부분:

• fib(3)과 fib(2)는 여러 번 호출됩니다:

  • fib(3)은 fib(5)와 fib(4)에서 각각 2번 호출됩니다.
  • fib(2)도 fib(3)과 fib(4)에서 각각 3번 호출됩니다.

  호출 횟수 최종 계산

1. fib(5) 호출: 1번
2. fib(4) 호출: 1번
3. fib(3) 호출: 3번
4. fib(2) 호출: 3번
5. fib(1) 호출: 3번
6. fib(0) 호출: 3번

총 호출 횟수 = 1 + 1 + 3 + 3 + 3 + 3 = 15번

중복 호출:

• fib(3)은 2번 호출됩니다 (fib(5)와 fib(4)에서)
• fib(2)는 3번 호출됩니다 (fib(3)와 fib(4)에서)

최종 정리

1. fib(5)에서 시작하여 재귀적으로 호출되는 모든 함수는 각각 실행될 때마다 1번씩 호출됩니다.
2. 중복 호출은 fib(3)과 fib(2)가 여러 번 호출되는 것에 의해 발생합니다.
3. 호출 횟수는 총 15번, 리턴 횟수는 5번입니다.

중복 호출이란, 같은 함수(fib(3)나 fib(2))가 여러 번 호출되는 과정에서 하나의 호출이 여러 번 실행될 때 발생합니다. fib(5)에서 fib(4)와 fib(3)을 호출하면서 각각 그 안에서 또 다른 함수들을 호출하게 되므로 호출 횟수는 점점 증가하게 되는 것이죠.

---

포인터 변수 및 주소 연산자

주요 개념

1. 포인터와 주소 연산자 사용 시 (값을 변경할 때)

   포인터 사용:

포인터는 변수의 주소를 가리키는 변수입니다. 포인터를 사용하면 해당 변수의 값을 직접 수정할 수 있습니다. 이를 간접 참조 (dereferencing)라고 합니다.

예를 들어, *i는 i가 가리키는 주소에 있는 값을 수정할 수 있게 해줍니다.

int x = 10;
int *i = &x;  // x의 주소를 i에 저장
*i = 20;      // i가 가리키는 주소에 있는 값을 20으로 변경 -> 즉, x = 20

여기서 *i = 20;은 i가 가리키는 변수, 즉 x의 값을 20으로 바꾸는 것입니다. 이 방식은 변수 x의 값을 함수 외부에서도 변경할 수 있게 해줍니다.

주소 연산자 (&)와 포인터:

주소 연산자 &는 변수의 메모리 주소를 반환합니다. 이를 포인터 변수에 할당하여 해당 주소에 직접 접근하고 값을 변경할 수 있게 됩니다.

int x = 10;
int *i = &x;  // &x는 x의 주소
20

2. 포인터 없이 값만 전달할 때 (값 복사)

   값 전달 방식:

값을 직접 전달하면, 값 복사 방식이 사용됩니다. 이 경우 함수 안에서 값이 변경되더라도 원래 변수의 값은 바뀌지 않습니다.

void f(int j) {
    j = 30;  // 함수 내부에서만 j의 값이 변경됨
}

int main() {
    int x = 10;
    f(x);  // x는 10이고, f()에서 j만 30으로 바뀌는 것
    printf("%d\n", x);  // x는 여전히 10
}
0

위 코드에서 f(x)가 호출되었을 때, x의 값은 변경되지 않습니다. x는 값 복사 방식으로 f() 함수로 전달되기 때문에, f() 내부에서 j의 값을 변경해도 원래 x의 값에는 영향을 주지 않습니다.

3. 포인터를 사용하지 않았을 때 (값 전달 방식의 특징)

int f(int j) {
    j += 5;  // j는 함수 내부에서만 변경
    return j;
}

int main() {
    int x = 10;
    printf("%d\n", f(x));  // x의 값은 여전히 10
    printf("%d\n", x);     // x의 값은 여전히 10
}

• f(x)에서 x를 값으로 전달하면, x의 값이 복사되어 f() 함수의 j에 저장됩니다. 그래서 f() 함수에서 j 값을 변경해도 원래 x의 값은 영향을 받지 않습니다.

  결론:

1. 포인터 사용 시:

   • 변수의 주소를 직접 사용하여, 그 주소에 있는 값을 직접 변경할 수 있습니다.
   • 예: *i = 20; -> i가 가리키는 주소의 값을 20으로 변경.

2. 값 전달 방식 (포인터 없이):

   • 변수의 값만 복사하여 함수에 전달됩니다.
   • 함수 내에서 값이 변경되더라도, 원래 변수의 값은 변경되지 않습니다.

즉, 포인터를 사용하면 함수 내에서 원본 값이 변경될 수 있고, 포인터를 사용하지 않으면 함수 내에서 값 복사로 원본 값에 영향을 미치지 않게 됩니다.

---

문제

C 언어로 작성된 프로그램이다. 이를 실행한 결과를 쓰시오.

#include <stdio.h>

int f(int *i, int j) {
    *i += 5;  // 포인터 i가 가리키는 값에 5를 더한다.
    return (2 * *i + ++j);  // *i는 이제 x + 5이고, j는 먼저 증가한 후 사용된다.
}

int main(void) {
    int x = 10, y = 20;

    printf("%d", f(&x, y));  // f(&x, y) 호출
    printf("%d %d\n", x, y);  // x와 y의 값 출력
}

1. f(&x, y) 호출:

• f() 함수가 호출될 때, x의 주소와 y의 값이 전달된다.

• &x는 x의 주소를 전달하는 것이고, y는 값 복사 방식으로 전달된다.

  • i는 &x로 x의 주소를 가리키고, j는 y의 값인 20을 받는다.

  2. *i += 5; 실행:

• i는 x의 주소를 가리킨다.

• 따라서 *i는 x의 값이고, *i += 5;는 x의 값을 5만큼 증가시킨다.

  • 원래 x = 10이었고, x의 값은 15로 변경된다.

  3. ++j 실행:

• ++j는 전위 증가 연산자이므로, 먼저 j 값을 증가시키고 그 후에 값을 사용한다.

  • j는 20에서 1이 증가하여 j = 21이 된다.

  4. return(2 * *i + ++j); 실행:

• *i는 15 (이전 단계에서 x가 15로 변경되었기 때문)이고, j는 21이다.

• 2 * 15 + 21을 계산하면, 30 + 21 = 51이 된다.

• f() 함수는 51을 리턴한다.

  5. printf("%d", f(&x, y));:

• f(&x, y)가 51을 리턴했으므로, 51이 출력된다.

  6. printf("%d %d\n", x, y);:

• x는 15로 변경되었고, y는 20으로 변경되지 않았다.

  • 따라서 x는 15, y는 20이 출력된다.

  최종 결과:

• 첫 번째 출력: 51 (이 값은 f(&x, y)에서 리턴한 값)

• 두 번째 출력: 15 20 (이 값은 x와 y의 현재 값)

  핵심 포인트:

1. 포인터 사용:

   • f(&x, y)에서 x의 주소를 전달하면서 *i += 5로 x의 값을 직접 변경한다.

2. 값 전달:

   • y는 값으로 전달되어 j의 값은 복사되어 함수 내에서 변경되지만, 원래 y의 값은 변경되지 않는다.

3. ++j:

   • ++j는 전위 증가 연산자로, 먼저 j를 증가시키고 그 값을 사용한다.

결과 요약

• 출력 값은 51 15 20이다.
  • 51은 f(&x, y)의 반환값이고,
  • x = 15, y = 20은 각각 최종 값이다.