Linkage and Recursion (2/2)
연결과 순환호출 C언어
Contents
1️⃣ 연결(Linkage)
2️⃣ 순환 (Recursion)
Summary of Linkage and Recursion
(연결과 순환 호출 요약)
1. Linkage (연결)
Linkage는 다른 범위에 속하는 변수들을 서로 연결하는 개념이다. 이는 주로 C언어에서 저장 유형 지정자를 통해 외부에서 정의된 변수와 함수를 연결할 때 사용된다.
Types of Linkage (연결의 종류):
External Linkage (외부 연결): 파일 간에 변수를 공유할 수 있도록
extern키워드를 사용하여 외부 변수에 접근한다.Internal Linkage (내부 연결): 하나의 파일 내에서만 변수를 사용할 수 있으며,
static키워드를 사용하여 파일 내에서만 접근 가능하다.No Linkage (무연결): 블록 내에서만 유효한 지역 변수로, 연결되지 않는 변수이다.
Example (예제):
extern int global_var;로 다른 파일에서 정의된 변수를 사용할 수 있다.static int local_var;로 파일 내에서만 사용할 수 있는 변수를 정의한다.
2. Recursion (순환 호출)
Recursion은 함수가 자기 자신을 호출하여 문제를 반복적으로 해결하는 방식이다. 재귀적 접근은 큰 문제를 작은 단위로 나누어 해결할 수 있게 해 주며, 수학적 계산, 분할 정복 알고리즘, 탐색 문제 등에서 유용하게 사용된다.
Basic Structure (기본 구조):
Base Case (기저 사례): 재귀 호출이 멈추는 조건을 정의한다. (예:
n == 1일 때 함수가 종료)Recursive Case (재귀 사례): 자기 자신을 호출하여 문제를 더 작은 단위로 나뉜다.
Example (예제):
Factorial (팩토리얼):
factorial(n) = n * factorial(n - 1)을 통해 n이 1이 될 때까지 계속해서 자기 자신을 호출한다.Tower of Hanoi (하노이 탑):
n-1개의 원판을 임시 위치로 옮긴 후, 가장 큰 원판을 목표 위치로 옮기고 다시n-1개의 원판을 옮기는 재귀적 접근 방식이다.
Key Takeaways (핵심 요점)
Linkage는 변수를 다른 범위나 파일과 연결하여 사용할 수 있게 해 주며,
extern과static키워드를 통해 외부 및 내부 연결을 제어한다.Recursion은 문제를 작은 단위로 쪼개어 해결하는 방식으로, base case와 recursive case를 설정하여 자기 자신을 반복 호출한다.
Applications: Linkage는 여러 파일에서 변수와 함수의 가시성을 관리할 때 사용하고, Recursion은 하노이탑 문제, 팩토리얼 계산 등 다양한 재귀적 문제에 사용된다.
Overall, Linkage and Recursion are fundamental concepts in C programming that allow for modular code management and efficient problem-solving through repetitive structure.
연결과 순환호출 차시에서는 저장 유형 지정자(Storage Class Specifier)를 어떻게 연결하는지와 순환호출을 어떻게 사용하는지에 대해 살펴볼 예정이다.
저장 유형 지정자 연결 복습(Review of Storage Class Specifier)
저장 유형 지정자는 변수의 메모리 위치나 생명 주기를 제어하는 키워드로,
auto,register,static,extern등이 있다.예를 들어,
extern은 외부 파일에 선언된 변수를 다른 파일에서도 사용할 수 있게 연결하는 역할을 한다.
1️⃣ 연결(Linkage)
💡요약: 연결(Linkage)은 다른 범위에 있는 변수들을 서로 연결하여 사용할 수 있게 하는 개념이다. 이 개념을 이해하는 것이 중요한 이유는 여러 파일이나 다른 범위에 정의된 변수를 함께 활용할 수 있게 하기 때문이다. 이미지에서는 두 개의 다른 범위에 있는 변수가 연결되어 함께 사용되는 모습을 보여주고 있다.
외부 연결 (External Linkage): 외부 연결은 다른 파일이나 코드 블록에서 변수를 사용할 수 있게 연결하는 방식이다. 전역 변수에
extern키워드를 사용하여 외부에서 참조할 수 있도록 할 수 있다.내부 연결 (Internal Linkage): 내부 연결은 한 파일 내에서만 변수를 사용할 수 있도록 제한하는 방식이다.
static키워드를 사용하면 해당 변수는 파일 내부에서만 사용이 가능하다.무연결 (No Linkage): 무연결은 특정 함수 내에서만 변수를 사용할 수 있는 방식이다. 일반적인 지역 변수가 이에 해당되며, 함수 외부에서 접근할 수 없다.
연결 #1: 외부 연결 (External Linkage)
💡요약: 외부 연결은 전역 변수 (global variable)를 다른 파일에서도 사용할 수 있게 하는 방법인데, 이를 위해 extern 키워드를 사용한다. extern 키워드는 변수가 다른 파일에 정의되어 있음을 알리고, 해당 변수를 참조할 수 있게 한다. 예를 들어, file1.c에서 정의한 변수를 file2.c나 file3.c에서도 사용할 수 있도록 연결해 준다.
// 파일 1: file1.c
#include <stdio.h>
extern int global; // 외부 파일에서 정의된 변수를 참조함
void printGlobal() {
printf("Global: %d\n", global);
}
// 파일 2: file2.c
#include <stdio.h>
int global = 1; // 전역 변수 정의 및 초기화
int main() {
printGlobal(); // file1.c에 정의된 함수를 호출
return 0;
}
위의 예제에서 file2.c에서 정의한 global 변수를 file1.c에서도 extern 키워드를 사용하여 참조한. global 변수가 file1.c에서 정의된 printGlobal 함수에서 사용될 수 있도록 외부 연결이 설정되었다.
연결 #2: 외부 연결 예제 (Example of External Linkage)
linkage1.c
#include <stdio.h>
int all_files; // 전역 변수, 외부에서 접근 가능
static int this_file; // 정적 변수, 이 파일 내에서만 접근 가능
extern void sub(); // 다른 파일에서 정의된 함수 선언
int main(void)
{
sub(); // linkage2.c의 sub 함수 호출
printf("External Linkage Example2 %d\n", all_files); // all_files 값 출력 (10 출력 예상)
return 0;
}
linkage1.c에서는 all_files 변수가 전역으로 선언되어 다른 파일에서도 접근할 수 있다. static int this_file;로 선언된 this_file 변수는 이 파일 내부에서만 접근 가능하다. main 함수에서 sub() 함수를 호출하여 all_files 값을 변경한 후 출력한다.
linkage2.c
extern int all_files; // linkage1.c의 all_files 변수를 참조
void sub(void)
{
all_files = 100; // all_files 변수에 10 할당
}
linkage2.c에서는 extern int all_files; 선언을 통해 linkage1.c의 all_files 변수와 연결한니다. sub 함수는 all_files에 10을 할당하며, 이 값은 main 함수에서 출력될 때 사용된다.
static
함수 앞에 static 키워드를 붙이면 해당 함수는 선언된 파일 내에서만 사용할 수 있게 된다.즉, Internal Linkage (내부 연결)을 가지게 되어 다른 파일에서는 호출할 수 없다.
Static Function
static키워드가 붙은 함수는 해당 파일 내에서만 접근할 수 있는 함수이다. 예를 들어f1()함수는static으로 선언되었기 때문에sub.c에서만 호출 가능하다. 다른 파일에서는 사용할 수 없다.
Extern Function:
extern키워드를 사용하면 다른 파일에 선언된 함수를 참조할 수 있다.f2()는extern으로 선언되어main.c에서sub.c의f2()함수를 호출할 수 있다.
main.c
#include <stdio.h>
// extern void f1(); // f1()은 static으로 선언되어 있어 main.c에서 접근 불가
extern void f2(); // f2()는 다른 파일에서 정의되어 있지만, 외부에서 접근 가능
int main(void)
{
f2(); // f2() 호출, sub.c의 f2() 함수가 실행됨
return 0;
}
main.c에서는 f2() 함수를 외부 파일에서 참조하여 호출할 수 있지만, f1()은 static으로 선언되어 있어서 extern void f1();로 선언해도 에러가 발생하므로 주석 처리되어 있다.
sub.c
#include <stdio.h>
static void f1() // 이 함수는 sub.c 내에서만 접근 가능
{
printf("f1()가 호출되었습니다.\n");
}
void f2() // 다른 파일에서 접근할 수 있음
{
printf("f2()가 호출되었습니다.\n");
}
sub.c에서는 f1() 함수가 static으로 선언되어 내부에서만 접근이 가능하며, 외부에서는 호출할 수 없다. 반면, f2()는 일반 함수로 선언되어 main.c에서도 호출할 수 있다.
static으로 선언된 f1함수도 불러오려하고면 위와 같은 오류가 뜬다.
static으로 선언된 f1함수는 코멘트 처리하였더니 f2 함수가 정상적으로 출력된다.
연결 #3:
Referencing a Global Variable with Extern in a Block
(블록에서 extern을 이용한 전역 변수 참조)
extern 키워드를 사용하여 Block (블록) 안에서 전역 변수(global variable)를 참조하는 방법을 알아보자. 전역 변수는 함수 외부에 선언된 변수로, 프로그램 전체에서 접근이 가능하다. 하지만 함수 내부의 특정 블록 안에서 전역 변수를 명시적으로 참조하고자 할 때는 extern 키워드를 사용할 수 있다.
Global Variable (전역 변수):
- 전역 변수는 함수 외부에 선언되어 프로그램 전체에서 접근할 수 있는 변수이다. 여기서
int x = 50;은 전역 변수로 선언되었다.
- 전역 변수는 함수 외부에 선언되어 프로그램 전체에서 접근할 수 있는 변수이다. 여기서
Extern Keyword in a Block:
extern키워드는 블록 안에서 전역 변수를 참조할 때 사용할 수 있다. 이 예제에서,main함수 안의 블록에서extern int x;로 전역 변수x를 참조하고 있다.
#include <stdio.h>
int x = 50; // 전역 변수 선언
int main(void)
{
int x = 100; // 지역 변수 선언
{
extern int x; // 전역 변수 x를 참조
printf("x= %d\n", x); // 전역 변수 x의 값(50) 출력
}
return 0;
}
이 코드에서 int x = 50;은 전역 변수로 선언되어 있고, main 함수 내에서는 int x = 100;으로 같은 이름의 지역 변수를 선언했다. 중첩된 블록 내에서 extern int x;를 사용하여 전역 변수 x를 참조하고 있다. printf는 전역 변수의 값인 50을 출력한다.
연결 #4: Which Storage Class to Use?
(어떤 저장 유형을 사용하여 하는가?)
💡요약: 저장 유형은 변수의 Scope (범위)와 Lifeime (생존 시간)을 결정하는 중요한 요소소이다. 적절한 저장 유형을 선택하면 메모리 관리와 코드의 효율성을 높일 수 있다. 이 슬라이드는 다양한 저장 유형을 설명하고, 각각의 용도와 특징을 이해하는 데 도움을 준다.
아래의 이미지에서는 각 저장 유형의 키워드, 정의 위치, 범위, 생존 시간을 정리한 표를 보여준다. 예를 들어, auto와 register는 함수 내에서만 접근할 수 있으며 함수가 종료되면 메모리에서 사라지게 된다. 반면에 extern과 static 전역 변수는 프로그램이 종료될 때까지 메모리에 유지된다.
일반적으로 자동 저장 유형 (auto)을 사용하는 것이 권장된다. auto는 함수 내에서 변수를 선언할 때 기본적으로 적용되며, 함수가 종료되면 메모리에서 사라지기 때문에 효율적이다. 대부분의 지역 변수는 auto로 선언되며, 별도로 auto 키워드를 지정하지 않아도 된다.
하지만, 함수 호출이 끝나도 값을 유지해야 하는 경우에는 지역 정적 (static) 변수를 사용하는 것이 좋다. 예를 들어, 함수가 몇 번 호출되었는지 카운트하거나, 특정 값이 함수 호출 간에 유지되어야 할 때 static을 사용하면 값이 사라지지 않고 다음 호출 시에도 유지된다.
또한, 여러 함수에서 공유해야 하는 변수가 있다면 외부 참조 변수 (extern)를 사용한다. extern 키워드를 통해 여러 파일에서 전역 변수를 공유할 수 있으며, 대규모 프로젝트에서 특정 설정 값이나 공용 변수를 여러 파일에 걸쳐 사용해야 할 때 유용하다.
이렇게 자동 저장 유형을 기본으로 하고, 필요한 경우에 따라 static이나 extern을 적절히 사용하는 것이 효율적이다.
💡예제:
auto : 기본적으로 지역 변수는 auto 저장 유형을 가진다. 별도로 auto 키워드를 지정하지 않아도 된다.
#include <stdio.h>
void autoExample() {
int count = 0; // auto 저장 유형 (기본 지역 변수)
count++;
printf("Count: %d\n", count);
}
int main() {
autoExample(); // 출력: Count: 1
autoExample(); // 출력: Count: 1 (함수 호출이 끝나면 count는 초기화됨)
return 0;
}
static : 키워드를 사용하면 함수 호출이 끝나도 값이 유지된다. 함수가 호출될 때마다 이전의 값을 기억하고 이어서 동작한다.
#include <stdio.h>
void staticExample() {
static int count = 0; // static 저장 유형
count++;
printf("Count: %d\n", count);
}
int main() {
staticExample(); // 출력: Count: 1
staticExample(); // 출력: Count: 2 (이전 값 유지)
staticExample(); // 출력: Count: 3
return 0;
}
extern : 키워드를 사용하면 다른 파일에서 선언된 전역 변수를 참조할 수 있다. 예를 들어, 두 파일에서 전역 변수를 공유하고자 할 때 유용하다.
// file1.c
#include <stdio.h>
int sharedVar = 10; // 전역 변수 정의
void printSharedVar() {
printf("Shared Variable: %d\n", sharedVar);
}
// file2.c
#include <stdio.h>
extern int sharedVar; // 외부 참조 변수 선언
int main() {
sharedVar = 20; // 외부 참조 변수 값 수정
printSharedVar(); // 출력: Shared Variable: 20
return 0;
}
위 예제에서 file1.c에 정의된 sharedVar는 file2.c에서 extern을 통해 참조되고 있다. file2.c에서 값을 변경하면 file1.c에서도 변경된 값이 출력된다.
위의 예제들과 같이, auto를 기본으로 사용하고, 값 유지가 필요하면 static, 여러 파일에서 변수 공유가 필요하면 extern을 사용하는 것이 좋다.
2️⃣ 순환 (Recursion)
💡요약: 순환 (Recursion)은 함수가 자기 자신을 호출하는 프로그래밍 기법이다. 이를 통해 문제를 작은 단위로 나누어 해결할 수 있다. 예를 들어, 아래 이미지에서는 팩토리얼 (Factorial)을 계산하는 예를 보여준다. 팩토리얼 계산에서, 숫자 n의 팩토리얼은 n * (n-1)!로 정의되며, 이 과정에서 계속해서 자기 자신을 호출하는 순환 구조를 가진다.
💡예제:
팩토리얼 계산:
5! = 5 * 4 * 3 * 2 * 1 = 120피보나치 수열: 피보나치 수열의 n번째 값은
(n-1)번째 + (n-2)번째값으로 정의되어, 함수가 계속해서 자기 자신을 호출하여 값을 계산한다.
순환 #1: Calculating Factorial Using Recursion
(팩토리얼 구하기 - 순환 호출 사용)
💡요약: 팩토리얼 (Factorial)을 구하는 방법 중 하나는 순환 호출 (Recursion)을 사용하는 것이다. Recursion을 통해 함수가 자기 자신을 반복적으로 호출하면서 문제를 해결할 수 있다. 예를 들어, 5!를 계산하려면 5 * 4!을 계산해야 하고, 4!를 구하려면 4 * 3!을 구해야 하는 방식으로 진행된다
💡예제: 아래 코드를 통해 factorial(5)을 호출하면 5!가 계산된다.
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // Base Case
else return n * factorial(n - 1); // Recursive Case
}
int main() {
int result = factorial(5);
printf("5! = %d\n", result); // 출력: 5! = 120
return 0;
}
자기 자신을 호출하여 팩토리얼 값을 계산하는 코드이다. 사람 캐릭터들이 5!, 4!, 3! 등 각 단계에서 계산되는 과정을 설명하며, 마지막에 1!에 도달했을 때 결과값 1로 순환이 종료된다.
순환 #2: Structure of a Recursive Function
(순환 함수의 구조)
💡요약: 순환 함수 (Recursive Function)는 기저 사례 (Base Case)와 재귀 호출 사례 (Recursive Case)로 구분 된다. Recursion을 사용하면 함수가 자기 자신을 반복적으로 호출하면서 문제를 단계별로 해결할 수 있게 된다. 예를 들어, 팩토리얼 계산 함수에서, n이 1 이하일 때 함수는 1을 반환하며 종료되고, 그렇지 않으면 n * factorial(n - 1)을 통해 재귀적으로 자기 자신을 호출한다.
Base Case (기저 사례): 재귀 호출을 멈추는 부분이다. 여기서
if (n <= 1) return 1;이 기저 사례에 해당하며, 이 조건이 없으면 함수가 계속 반복되어 무한 루프에 빠질 수 있다.Recursive Case (재귀 사례): 함수가 자기 자신을 호출하는 부분이다. 이 예제에서는
else return n * factorial(n - 1);이 재귀 사례이다.
순환 #3: Calculating Factorial - Call Sequence
(팩토리얼 구하기 - 호출 순서)
💡요약:팩토리얼 (Factorial)을 계산할 때 순환 호출 (Recursive Call)이 이루어지는 순서와 그 과정을 단계별로 확인한다. factorial(3)을 계산하기 위해 함수가 계속해서 자기 자신을 호출하는 방식으로 factorial(2)와 factorial(1)까지 계산한 후, 마지막에 모든 결과를 곱하여 최종 값을 반환하게 된다.
factorial(3)에서 시작하여 factorial(1)까지 순차적으로 호출된 후, 반환값이 차례로 계산되어 최종 결과가 나온다. Recursive Call을 통해 팩토리얼을 단계적으로 계산하였다. 함수 호출 순서를 이해하면, 최종 결과가 반환되는 과정을 쉽게 파악할 수 있다. 각 함수가 호출되어 결과를 반환하고, 반환된 값을 곱하면서 최종 값을 얻는다.
순환 #4: Factorial Calculation (팩토리얼 계산)
💡요약: 아래 예제에서는 factorial 함수가 호출되는 순서를 보여준다. factorial(5)가 factorial(4)를 호출하고, 계속해서 factorial(1)까지 호출한 후, 모든 값을 곱하여 5! = 120을 계산하는 과정을 보여준다.
#include <stdio.h>
long factorial(int n) {
printf("factorial(%d)\n", n); // 현재 함수 호출을 출력
if (n <= 1) return 1; // Base Case
else return n * factorial(n - 1); // Recursive Case
}
int main(void) {
int n;
printf("정수를 입력하십시오: ");
scanf("%d", &n);
printf("%d!은 %ld입니다.\n", n, factorial(n)); // 팩토리얼 결과 출력
return 0;
}
순환 #5: Converting to Binary Using Recursion
(2진수 형식으로 출력하기 - 순환 호출 사용)
💡요약:C 언어에서는 기본적으로 정수를 2진수(Binary)로 출력하는 기능이 없기 때문에, Recursion (순환 호출)을 이용하여 숫자를 2진수로 변환하는 방법을 구현할 수 있다. 이 과정은 숫자를 2로 나누고, 나머지를 기록한 후, 나눈 몫을 가지고 다시 2로 나누는 방식으로 이루어진다. 최종적으로 나머지들을 역순으로 읽으면 2진수가 된다.
Recursive Division (순환 나누기): 숫자를 2로 나누고, 몫이
0이 될 때까지 반복하여 나머지를 구한다Reversing the Order (순서 뒤집기): 각 나머지들을 역순으로 읽어야 올바른 2진수를 얻을 수 있게 된다.
숫자 7을 2진수로 변환하는 과정을 단계별로 설명하고 있다. 7을 2로 나누면 몫 3과 나머지 1이 나오고, 3을 다시 2로 나누어 몫 1과 나머지 1을 구하는 식으로 진행된다. 마지막으로 1을 2로 나누었을 때 몫 0과 나머지 1이 나온다. 이 과정을 역순으로 읽으면 111이 되어 7의 2진수 표현임을 알 수 있다.
7을 2로 나눔 → 몫: 3, 나머지: 1
3을 2로 나눔 → 몫: 1, 나머지: 1
1을 2로 나눔 → 몫: 0, 나머지: 1
나머지를 역순으로 읽으면, 111이 되어 7의 2진수 표현이 된다.
순환 #6: Printing in Binary Format Using Recursion
(2진수 형식으로 출력하기 - 순환 호출 사용)
#include <stdio.h>
void print_binary(int x) {
if (x > 0) {
print_binary(x / 2); // Recursive call with quotient
printf("%d", x % 2); // Print remainder
}
}
int main(void) {
print_binary(9); // Convert 9 to binary
printf("\n");
return 0;
}
Recursion을 통해 정수를 2로 나누고 나머지를 기록하여 2진수로 변환할 수 있다.
모든 재귀 호출이 완료된 후 나머지를 출력하여 최종적으로 2진수 값을 얻는다.
순환 #7: Finding the Greatest Common Divisor
(최대 공약수 구하기)
💡요약: 최대 공약수(GCD)를 구하는 방법 중 하나로 Euclidean Algorithm (유클리드 호제법)이 있다. 이 방법은 두 수의 나머지를 이용해 최대 공약수를 점차적으로 구해 나가는 방식이다. 이 방법에 따르면, 두 수 x와 y의 최대 공약수는 y와 x를 y로 나눈 나머지(x % y)의 최대 공약수와 같다. 또한, 만약 y가 0이 되면, 최대 공약수는 x가 된다.
Euclidean Algorithm (유클리드 호제법):
- 두 수의 최대 공약수를 구할 때, 나머지를 이용하여 점진적으로 값을 줄여가는 알고리즘이다.
Recursive Calculation (재귀 계산):
- 이 알고리즘은 재귀적으로 정의되며,
gcd(x, y) = gcd(y, x % y)로 계속 반복하여, y가 0이 되면(gcd(x, 0) = x) 그때의 x 값이 최대 공약수가 된다.
- 이 알고리즘은 재귀적으로 정의되며,
#include <stdio.h>
int gcd(int x, int y) {
if (y == 0) // Base case: y가 0일 때
return x;
else
return gcd(y, x % y); // Recursive case: gcd(y, x % y)
}
int main(void) {
printf("%d\n", gcd(30, 20)); // 30과 20의 최대 공약수 출력
return 0;
}
gcd(30, 20)을 호출하여 최대 공약수를 구하는 예제이다. 이 코드에서 30과 20의 최대 공약수를 계산한 결과 10이 출력되었다.
