# Linkage and Recursion (2/2)

**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)

**<mark>💡요약:</mark>** 연결(Linkage)은 다른 범위에 있는 변수들을 서로 연결하여 사용할 수 있게 하는 개념이다. 이 개념을 이해하는 것이 중요한 이유는 여러 파일이나 다른 범위에 정의된 변수를 함께 활용할 수 있게 하기 때문이다. 이미지에서는 두 개의 다른 범위에 있는 변수가 연결되어 함께 사용되는 모습을 보여주고 있다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731297631721/b28d82cb-159e-4180-89b7-4bd3f6cb6315.png align="center")

* **외부 연결 (External Linkage)**: 외부 연결은 다른 파일이나 코드 블록에서 변수를 사용할 수 있게 연결하는 방식이다. 전역 변수에 `extern` 키워드를 사용하여 외부에서 참조할 수 있도록 할 수 있다.
    
* **내부 연결 (Internal Linkage)**: 내부 연결은 한 파일 내에서만 변수를 사용할 수 있도록 제한하는 방식이다. `static` 키워드를 사용하면 해당 변수는 파일 내부에서만 사용이 가능하다.
    
* **무연결 (No Linkage)**: 무연결은 특정 함수 내에서만 변수를 사용할 수 있는 방식이다. 일반적인 지역 변수가 이에 해당되며, 함수 외부에서 접근할 수 없다.
    

---

## 연결 #1: **외부 연결 (External Linkage)**

**<mark>💡요약: </mark>** 외부 연결은 **전역 변수 (global variable)**를 다른 파일에서도 사용할 수 있게 하는 방법인데, 이를 위해 **extern** 키워드를 사용한다. `extern` 키워드는 변수가 다른 파일에 정의되어 있음을 알리고, 해당 변수를 참조할 수 있게 한다. 예를 들어, `file1.c`에서 정의한 변수를 `file2.c`나 `file3.c`에서도 사용할 수 있도록 연결해 준다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731299303459/42771942-3ab4-4b3a-8f9c-99fbc073fd16.png align="center")

```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;
}
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731299787501/6c5e9b6e-d6db-4b82-adbb-ca75af2a742f.png align="center")

위의 예제에서 `file2.c`에서 정의한 `global` 변수를 `file1.c`에서도 `extern` 키워드를 사용하여 참조한. `global` 변수가 `file1.c`에서 정의된 `printGlobal` 함수에서 사용될 수 있도록 외부 연결이 설정되었다.

---

## 연결 #2: **외부 연결 예제 (Example of External Linkage)**

**linkage1.c**

```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

```c
extern int all_files; // linkage1.c의 all_files 변수를 참조

void sub(void)
{
    all_files = 100; // all_files 변수에 10 할당
}
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731300234240/e50840de-ea81-4624-be58-b2175d4c1f79.png align="center")

`linkage2.c`에서는 `extern int all_files;` 선언을 통해 `linkage1.c`의 `all_files` 변수와 연결한니다. `sub` 함수는 `all_files`에 10을 할당하며, 이 값은 `main` 함수에서 출력될 때 사용된다.

---

### `static`

함수 앞에 **static** 키워드를 붙이면 해당 함수는 선언된 파일 내에서만 사용할 수 있게 된다.즉, **Internal Linkage (내부 연결)**을 가지게 되어 다른 파일에서는 호출할 수 없다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731300805281/c6787d63-d870-4177-9750-439cb632726e.png align="center")

* **Static Function**
    
    * `static` 키워드가 붙은 함수는 해당 파일 내에서만 접근할 수 있는 함수이다. 예를 들어 `f1()` 함수는 `static`으로 선언되었기 때문에 `sub.c`에서만 호출 가능하다. 다른 파일에서는 사용할 수 없다.
        
* **Extern Function**:
    
    * `extern` 키워드를 사용하면 다른 파일에 선언된 함수를 참조할 수 있다. `f2()`는 `extern`으로 선언되어 `main.c`에서 `sub.c`의 `f2()` 함수를 호출할 수 있다.
        

#### main.c

```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

```c
#include <stdio.h>

static void f1() // 이 함수는 sub.c 내에서만 접근 가능
{
    printf("f1()가 호출되었습니다.\n");
}

void f2() // 다른 파일에서 접근할 수 있음
{
    printf("f2()가 호출되었습니다.\n");
}
```

`sub.c`에서는 `f1()` 함수가 `static`으로 선언되어 내부에서만 접근이 가능하며, 외부에서는 호출할 수 없다. 반면, `f2()`는 일반 함수로 선언되어 `main.c`에서도 호출할 수 있다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731301150440/f6193c07-69b8-46d2-a6a2-5ac4979e41be.png align="center")

static으로 선언된 f1함수도 불러오려하고면 위와 같은 오류가 뜬다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731301225290/985557cb-533f-467a-9c74-04ac948ac4a5.png align="center")

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`를 참조하고 있다.
        

```c
#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;
}
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731301875305/dd42d5ef-0d94-4630-b9a8-dd7ecc6ace14.png align="center")

이 코드에서 `int x = 50;`은 전역 변수로 선언되어 있고, `main` 함수 내에서는 `int x = 100;`으로 같은 이름의 지역 변수를 선언했다. 중첩된 블록 내에서 `extern int x;`를 사용하여 전역 변수 `x`를 참조하고 있다. `printf`는 전역 변수의 값인 `50`을 출력한다.

---

### 연결 #4: Which Storage Class to Use?  
(어떤 저장 유형을 사용하여 하는가?)

**<mark>💡요약: </mark>** 저장 유형은 변수의 **Scope (범위)**와 **Lifeime (생존 시간)**을 결정하는 중요한 요소소이다. 적절한 저장 유형을 선택하면 메모리 관리와 코드의 효율성을 높일 수 있다. 이 슬라이드는 다양한 저장 유형을 설명하고, 각각의 용도와 특징을 이해하는 데 도움을 준다.

아래의 이미지에서는 각 저장 유형의 키워드, 정의 위치, 범위, 생존 시간을 정리한 표를 보여준다. 예를 들어, `auto`와 `register`는 함수 내에서만 접근할 수 있으며 함수가 종료되면 메모리에서 사라지게 된다. 반면에 `extern`과 `static` 전역 변수는 프로그램이 종료될 때까지 메모리에 유지된다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731302065571/078e1f2b-3cf4-41de-b76b-4e246c676c41.png align="center")

일반적으로 **자동 저장 유형 (auto)**을 사용하는 것이 권장된다. `auto`는 함수 내에서 변수를 선언할 때 기본적으로 적용되며, 함수가 종료되면 메모리에서 사라지기 때문에 효율적이다. 대부분의 지역 변수는 `auto`로 선언되며, 별도로 `auto` 키워드를 지정하지 않아도 된다.

하지만, **함수 호출이 끝나도 값을 유지해야 하는 경우**에는 **지역 정적 (static)** 변수를 사용하는 것이 좋다. 예를 들어, 함수가 몇 번 호출되었는지 카운트하거나, 특정 값이 함수 호출 간에 유지되어야 할 때 `static`을 사용하면 값이 사라지지 않고 다음 호출 시에도 유지된다.

또한, **여러 함수에서 공유해야 하는 변수**가 있다면 **외부 참조 변수 (extern)**를 사용한다. `extern` 키워드를 통해 여러 파일에서 전역 변수를 공유할 수 있으며, 대규모 프로젝트에서 특정 설정 값이나 공용 변수를 여러 파일에 걸쳐 사용해야 할 때 유용하다.

이렇게 자동 저장 유형을 기본으로 하고, 필요한 경우에 따라 **static**이나 **extern**을 적절히 사용하는 것이 효율적이다.

**<mark>💡예제:</mark>**

`auto` : 기본적으로 지역 변수는 `auto` 저장 유형을 가진다. 별도로 `auto` 키워드를 지정하지 않아도 된다.

```c
#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;
}
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731307355082/c7f6b08e-3a2d-4898-be4c-18811a43dd6b.png align="center")

`static` : 키워드를 사용하면 함수 호출이 끝나도 값이 유지된다. 함수가 호출될 때마다 이전의 값을 기억하고 이어서 동작한다.

```c
#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;
}
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731307385098/d54cbc8d-a692-478b-ac27-470a6dbcd15a.png align="center")

`extern` : 키워드를 사용하면 다른 파일에서 선언된 전역 변수를 참조할 수 있다. 예를 들어, 두 파일에서 전역 변수를 공유하고자 할 때 유용하다.

```c
// 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;
}
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731307532744/1779e9aa-5dff-4c26-ba2b-df65979247f2.png align="center")

위 예제에서 `file1.c`에 정의된 `sharedVar`는 `file2.c`에서 `extern`을 통해 참조되고 있다. `file2.c`에서 값을 변경하면 `file1.c`에서도 변경된 값이 출력된다.

위의 예제들과 같이, `auto`를 기본으로 사용하고, 값 유지가 필요하면 `static`, 여러 파일에서 변수 공유가 필요하면 `extern`을 사용하는 것이 좋다.

---

## **2️⃣** 순환 (Recursion)

**<mark>💡요약:</mark> 순환 (Recursion)**은 함수가 **자기 자신을 호출**하는 프로그래밍 기법이다. 이를 통해 문제를 작은 단위로 나누어 해결할 수 있다. 예를 들어, 아래 이미지에서는 **팩토리얼 (Factorial)**을 계산하는 예를 보여준다. 팩토리얼 계산에서, 숫자 `n`의 팩토리얼은 `n * (n-1)!`로 정의되며, 이 과정에서 계속해서 자기 자신을 호출하는 순환 구조를 가진다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731308512084/52075aca-12e2-4c17-93cb-3aae14525714.png align="center")

**<mark>💡예제:</mark>**

* **팩토리얼 계산**: `5! = 5 * 4 * 3 * 2 * 1 = 120`
    
* **피보나치 수열**: 피보나치 수열의 n번째 값은 `(n-1)번째 + (n-2)번째` 값으로 정의되어, 함수가 계속해서 자기 자신을 호출하여 값을 계산한다.
    

---

### 순환 #1: Calculating Factorial Using Recursion  
(팩토리얼 구하기 - 순환 호출 사용)

**<mark>💡요약: </mark> 팩토리얼 (Factorial)**을 구하는 방법 중 하나는 **순환 호출 (Recursion)**을 사용하는 것이다. **Recursion**을 통해 함수가 자기 자신을 반복적으로 호출하면서 문제를 해결할 수 있다. 예를 들어, `5!`를 계산하려면 `5 * 4!`을 계산해야 하고, `4!`를 구하려면 `4 * 3!`을 구해야 하는 방식으로 진행된다

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731309107221/ffb37b07-34c1-4ae0-a954-9b802147bbfe.png align="center")

**<mark>💡예제:</mark>** 아래 코드를 통해 `factorial(5)`을 호출하면 `5!`가 계산된다.

```c
#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;
}
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731309018651/60f3f49b-d4a1-4f7f-875b-b5555d2710e8.png align="center")

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731309062915/16a52a8a-0417-4b48-810d-59b9cec5b93a.png align="center")

자기 자신을 호출하여 팩토리얼 값을 계산하는 코드이다. 사람 캐릭터들이 `5!`, `4!`, `3!` 등 각 단계에서 계산되는 과정을 설명하며, 마지막에 `1!`에 도달했을 때 결과값 `1`로 순환이 종료된다.

---

### 순환 #2: Structure of a Recursive Function  
(순환 함수의 구조)

**<mark>💡요약: </mark>** 순환 함수 (Recursive Function)는 **기저 사례 (Base Case)**와 **재귀 호출 사례 (Recursive Case)**로 구분 된다. **Recursion**을 사용하면 함수가 자기 자신을 반복적으로 호출하면서 문제를 단계별로 해결할 수 있게 된다. 예를 들어, 팩토리얼 계산 함수에서, `n`이 `1` 이하일 때 함수는 `1`을 반환하며 종료되고, 그렇지 않으면 `n * factorial(n - 1)`을 통해 재귀적으로 자기 자신을 호출한다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731309613310/dae4fafd-a339-4b0f-b777-2e4cd64f9bf3.png align="center")

* **Base Case (기저 사례)**: 재귀 호출을 멈추는 부분이다. 여기서 `if (n <= 1) return 1;`이 기저 사례에 해당하며, 이 조건이 없으면 함수가 계속 반복되어 무한 루프에 빠질 수 있다.
    
* **Recursive Case (재귀 사례)**: 함수가 자기 자신을 호출하는 부분이다. 이 예제에서는 `else return n * factorial(n - 1);`이 재귀 사례이다.
    

---

### 순환 #3: **Calculating Factorial - Call Sequence**  
**(팩토리얼 구하기 - 호출 순서)**

**<mark>💡요약:</mark>팩토리얼 (Factorial)**을 계산할 때 **순환 호출 (Recursive Call)**이 이루어지는 순서와 그 과정을 단계별로 확인한다. `factorial(3)`을 계산하기 위해 함수가 계속해서 자기 자신을 호출하는 방식으로 `factorial(2)`와 `factorial(1)`까지 계산한 후, 마지막에 모든 결과를 곱하여 최종 값을 반환하게 된다.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731309710206/34556922-684d-4d3f-8f25-8e64bc61a5c8.png align="center")

`factorial(3)`에서 시작하여 `factorial(1)`까지 순차적으로 호출된 후, 반환값이 차례로 계산되어 최종 결과가 나온다. **Recursive Call**을 통해 팩토리얼을 단계적으로 계산하였다. 함수 호출 순서를 이해하면, 최종 결과가 반환되는 과정을 쉽게 파악할 수 있다. 각 함수가 호출되어 결과를 반환하고, 반환된 값을 곱하면서 최종 값을 얻는다.

---

## 순환 #4: Factorial Calculation (팩토리얼 계산)

**<mark>💡요약: </mark>** 아래 예제에서는 `factorial` 함수가 호출되는 순서를 보여준다. `factorial(5)`가 `factorial(4)`를 호출하고, 계속해서 `factorial(1)`까지 호출한 후, 모든 값을 곱하여 `5! = 120`을 계산하는 과정을 보여준다.

```c
#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;
}
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731310047295/1919c1fd-60ee-4cca-b750-582a017c5e1a.png align="center")

---

## 순환 #5: Converting to Binary Using Recursion  
(2진수 형식으로 출력하기 - 순환 호출 사용)

**<mark>💡요약:</mark>**C 언어에서는 기본적으로 정수를 **2진수(Binary)**로 출력하는 기능이 없기 때문에, **Recursion (순환 호출)**을 이용하여 숫자를 2진수로 변환하는 방법을 구현할 수 있다. 이 과정은 숫자를 2로 나누고, 나머지를 기록한 후, 나눈 몫을 가지고 다시 2로 나누는 방식으로 이루어진다. 최종적으로 나머지들을 역순으로 읽으면 2진수가 된다.

* **Recursive Division (순환 나누기)**: 숫자를 2로 나누고, 몫이 `0`이 될 때까지 반복하여 나머지를 구한다
    
* **Reversing the Order (순서 뒤집기)**: 각 나머지들을 역순으로 읽어야 올바른 2진수를 얻을 수 있게 된다.
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731310133470/9a4c9e1b-3e78-4a41-bd1a-350026353994.png align="center")

숫자 `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진수 형식으로 출력하기 - 순환 호출 사용)

```c
#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;
}
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731388136238/1b2ccc3a-2396-4ed9-b665-969ef5ad2c12.png align="center")

* **Recursion**을 통해 정수를 2로 나누고 나머지를 기록하여 2진수로 변환할 수 있다.
    
* 모든 재귀 호출이 완료된 후 나머지를 출력하여 최종적으로 2진수 값을 얻는다.
    

---

### 순환 #7: Finding the Greatest Common Divisor  
(최대 공약수 구하기)

**<mark>💡요약: </mark>** 최대 공약수(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 값이 최대 공약수가 된다.
        

```c
#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;
}
```

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1731388477959/83d80ef9-5b93-499e-bb0b-ed7f63f7c005.png align="center")

`gcd(30, 20)`을 호출하여 최대 공약수를 구하는 예제이다. 이 코드에서 `30`과 `20`의 최대 공약수를 계산한 결과 `10`이 출력되었다.

---