파이썬 알고리즘 043 | 재귀함수를 이용한 이진수 출력

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

10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용
해서 출력해야 합니다.
▣ 입력설명
첫 번째 줄에 10진수 N(1<=N<=1,000)이 주어집니다.
▣ 출력설명
첫 번째 줄에 이진수를 출력하세요.
▣ 입력예제 1
11
▣ 출력예제 1
1011

<내 풀이>

• 재귀함수를 어떻게 사용하는 지 아직 익숙하지 않다

def DFS(x) :
    if x//2 > 1 :
        k=str(x%2)
        DFS(x//2)
    else : 
        print(str(x//2) + k , end='')

if __name__=='__main__' : 
    n=int(input())
    DFS(n)

==> File "c:/Users/DONGYUN/Desktop/AA/AA.py", line 13, in
DFS(n)
File "c:/Users/DONGYUN/Desktop/AA/AA.py", line 7, in DFS
DFS(x//2)
File "c:/Users/DONGYUN/Desktop/AA/AA.py", line 7, in DFS
DFS(x//2)
File "c:/Users/DONGYUN/Desktop/AA/AA.py", line 9, in DFS
print(str(x//2) + k , end='')
UnboundLocalError: local variable 'k' referenced before assignment 라고 출력되는 걸로 보아 내가 원하는 대로 돌고 있긴 한데 결과값이 자꾸 이상하게 나온다

<풀이>

• 종료해주는 조건을 꼭 지정해놓아야 한다

def DFS(x) :
    if x==0 :
        return
    else : 
        print(x%2, end='') #이렇게 호출 위면 D11 D5 D2 D1..순서로 진행 
        DFS(x//2)        

if __name__=='__main__' : 
    n=int(input())
    DFS(n)

===> 그러나 이것 처럼 하면 처음으로 입력된 값부터 출력되는 거라서 값이 거꾸로 나온다

def DFS(x) :
   if x==0 :
       return
   else : 
       DFS(x//2)  #이렇게 호출 위여야 D0 D1 D2 D5 D11 순서로 진행
       print(x%2, end='')       

if __name__=='__main__' : 
	DFS(n)
   n=int(input())

===> 이렇게 호출 밑으로 프린트해야지 D1 D2 D5 D11이렇게 진행이 된다
좀 자세히 들어가보면 DFS(11)이 미처 일을 마무리하기 전에 D(5)가 호출이 되고 마무리 되기전에 2, 1, 0이 차례로 불려진다. 0이 되어서야 함수가 멈추고 그제서야 0부터 다시 거꾸로 값을 출력해주는 것이다

<반성점>

• 10진수와 2진수 변환 과정을 알지 못했다
• 재귀함수를 어떻게 사용해야 하는지 잘 감이 잡히지 않는다

<배운 점>

• 함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 부른다.
  반드시 탈출조건이 있어야 stack overflow를 방지할 수 있다.
  같은 행위가 반복될 때 재귀함수를 사용한다

• 2진수에서 10진수를 알아보는 법
  ==> 10진수 숫자가 있으면, 오른쪽부터 2의0제곱, 2의1제곱 의 값을 입력하고 1이 있는 부분에 있는 값들을 다 더하여 값을 도출

• 10진수에서 2진수를 알아보는 법
  ==> 10을 2로 계속해서 나누면서 나머지 값을 모으는 것
  

• 호출하는게 프린트보다 먼저 자리잡고 있으면
  나중의 값들부터 출력이 된다 *

<2회독 내 풀이>

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

if __name__=='__main__':
  n=int(input())
  DFS(n)