[Python-CodingTest] 6-1. 재귀함수를 이용한 이진수 출력

재귀함수를 이용한 이진수 출력

문제 정리

입력

11

처리 과정

1. 재귀함수 정의
2. x를 2로 나눈 나머지를 출력
3. 파라미터에 x 대신 x//2를 전달하면서 재귀함수 호출
4. 순서를 거꾸로 출력하기 위해서 출력문(2번)과 재귀문(3번)의 위치 바꾸기

출력

1011

내 답

import sys
sys.stdin = open("./input/in1.txt", "rt")

n=int(input())

res=list()
def recur(x,lst):
    if x>1:
        lst.insert(0,x%2)
        recur(x//2,lst) # 매개변수 업데이트 후 재귀
    else:
        lst.insert(0,x)

recur(n,res)

for x in res:
    print(x, end='')

풀이

import sys
sys.stdin = open("./input/in1.txt", "rt")

def DFS(v): # 재귀함수
    if v==0:
        return # 2. 함수 종료
    else:
        DFS(v//2) # 1. 이곳에서 스택프레임을 스택에 저장
        print(v%2, end='') # 3. 스택의 top부터 거꾸로 출력

if __name__=="__main__": # 메인 함수
    n=int(input())
    DFS(n)

정리

• stack frame: 스택 영역에 차례대로 저장되는 함수의 호출 정보

  스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.
  함수를 호출하면 해당 함수의 매개변수, 반환 주소값, 지역 변수 등의 스택 프레임이 스택에 저장된다.
  함수 호출이 끝난 뒤에, 스택의 top에 저장된 스택 프레임부터 스택에서 제거된다.

• 재귀함수와 스택

  def DFS(x):
  if x>0:
    print(x,end=' ') # 3 2 1
    DFS(x-1) # 재귀문
  DFS(3) # 재귀함수 호출
  

  재귀문보다 출력문이 먼저 위치한다면 3 2 1 출력

  def DFS(x):
  if x>0:
    DFS(x-1) # 재귀문
    print(x,end=' ') # 1 2 3
  DFS(3) # 재귀함수 호출
  

  출력문보다 재귀문이 먼저 위치한다면, 스택에 담아두었다가 거꾸로(top부터) 출력하기 때문에 1 2 3 출력

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기