재귀함수를 이용해 10진수를 2진수로 출력해보기

 

✏️ 목표

재귀함수를 사용하여 10진수를 2진수로 변환한 값을 출력해 보자.

 

 

 

❓ 10진수를 2진수로 변환하는 방법

10진수의 몫이 0이 될때까지 나누고 그 과정에서 나온 나머지를 아래에서 위로 차례로 작성하면 그 값이 해당 10진수의 2진수가 된다.

 

십진수 10을 2진수로 바꾸기 ex)

 

즉, 출력해야 하는 값은 각 몫에서의 나머지이다.

 

 

 

💻 코드 작성해보기

* 재귀 함수에서는 조건문(if ~ else)을 이용하여 실행을 제어한다.

 

< 의사코드 작성하기 >

1️⃣ 주 함수인 main함수를 정의하고 사용자의 입력을 하나 받아 그것을 int 형으로 변환한 뒤 n 변수에 넣어준다.

2️⃣ main 함수에서 실행시킬 n을 2진수를 바꾸기 위한 함수 binary를 정의한다.

3️⃣ 위의 진법 변환 방법에서 몫이 0이 될 때까지 10진수를 2로 나눈다 하였으므로 n이 0이 될 때 binary를 종료하도록 return을 적어준다.

4️⃣ n이 0이 아닌 경우에는 binary 자기 자신을 다시 호출해 그 안에 n을 2로 나눈 몫을 넣어준다.

5️⃣ binary 함수에서 출력되어야 하는 값은 각 단계에서의 n을 2로 나눈 나머지이다.

 

 

< Python 코드로 작성하기 >

 

def binary(n):
    if n == 0:
    	return
    else:
    	binary(n // 2)
        print(n % 2, end='')

def main():
    n = int(input())
    binary(n)

main()

 

 

 

📊 코드를 스택을 그려가며 분석해보기

재귀함수를 스택을 이용하여 분석하는 자세한 방법은 아래 글에서 볼 수 있다.

 

스택을 통해 재귀함수의 작동 과정에 대해 알아보자. (tistory.com)

스택을 통해 재귀함수의 작동 과정에 대해 알아보자.

 

 

우선, 스택에 함수 호출 정보가 쌓이는 과정부터 살펴보자.

 

10이라고 사용자로부터 입력을 받았다고 가정해 보자.

binary에 10이 인자로 들어가게 되고, binary 함수의 첫 호출이다. 따라서 스택에 binary(10)에 대한 정보가 쌓이게 된다.

10은 0이 아니므로 조건문이 False가 되어 else 다음의 binary(n // 2) 부분으로 이동하게 된다.

 

여기서 binary(5)가 새로 호출되게 된다. 아직 binary(10)의 함수가 끝까지(print문까지) 실행하여 마친 것이 아니므로 잠시 스택에 keep 해두고 binary(5)에 대한 정보가 스택에 새로 쌓인다.

 

이렇게 스택에 쌓이는 과정을 n이 0이 될 때까지 반복한다.

 

그림으로 나타내면 다음과 같다. (함수명인 binary는 b로 축약하여 작성하였다.)

 

n이 0이 되면 if n == 0 조건에서 True가 되어 b(0)에 대한 함수는 종료되게 된다. 이때, 스택에 기록되어 있는 복귀 위치에 따라 b(1) 함수에서의 b(n//2)가 적혀 있는 라인으로 복귀하게 된다. 스택에서도 b(0)에 대한 스택 프레임은 빠지게 된다.

 

이제 b(1) 함수가 하고 있던 작업을 마저 해야 하므로 print문이 실행된다. 따라서 1을 2로 나눈 나머지인 1이 화면에 출력되게 되고 b(1)의 스택 프레임에 있느 복귀 위치인 b(2)의 b(n//2)이 적혀 있는 라인으로 이동하면서 b(1)은 종료되게 된다. 역시 스택에서도 빠지게 된다.

 

이러한 작업을 스택이 모두 빌 때까지 반복하면 된다.

그림으로 나타내면 다음과 같다.

 

 

결과적으로 1, 2, 5, 10을 각각 2로 나눈 나머지인 1, 0, 1, 0이 공백 없이 연결되어 차례로 화면에 출력되게 된다.

 

< 결과 >

 

1010