<div id="readability-page-1" class="page"><div><h2 id="재귀함수를-이용한-이진수-출력">재귀함수를 이용한 이진수 출력</h2>
참고자료: <a href="https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8/lecture/26953?tab=curriculum&amp;speed=2">파이썬 알고리즘 문제풀이</a>
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
<ul>
<li>문제</li>
</ul>
자연수 n이 주어지면 재귀함수를 활용하여, 이진수의 형태로 출력하는 프로그램을 작성하시오.
<ul>
<li>입력예제</li>
</ul>
11
<ul>
<li>출력예제</li>
</ul>
1011
<h2 id="내-풀이">내 풀이</h2>
<pre><code>func binaryRecursion(_ dec: Int) {
 if dec &gt; 0 {
 binaryRecursion(dec/2)
 print(dec%2, terminator:"")
 }
}

let n = Int(readLine()!)!
binaryRecursion(n)</code></pre>
재귀함수를 활용한 반복구조이다. 스택을 제대로 이해했다면 해당 코드를 이해하는 데 큰 어려움은 없을 것이다. binaryRecursion함수를 간단하게 R이라고 한다면, [R(11), R(5), R(2), R(1), R(0)] 순서로 메모리(스택)에 쌓이게 된다. (R(0)에서 멈추는 이유는 dec가 0보다 같거나 작은 경우는 더이상 스스로를 호출(재귀)하지 않기 때문이다.
스택은 Last In First Out이기 때문에 R(0)부터 작업이 시작되는데, 0인 경우는 if dec &gt; 0 조건을 만족하지 못하여 아무런 추가 작업없이 함수가 종료된다. 그리고 R(1)의 4번째 줄로 돌아가고 호출 당시에 실행하지 못했던 print함수를 실행하고 종료된다. 나머지 R(2) -&gt; R(5) -&gt; R(11)도 같은 로직으로 실행되고 종료된다.
따라서 재귀함수에서는 스스로를 호출하는 위치가 굉장히 중요하다. 예를들면 binaryRecursion(dec/2)보다 print(dec%2)를 먼저 실행하면 원하는 해답인 '1011'이 아니라 '1101'이 호출되기 때문에 의도하지 않은 해답을 얻을 수 있다.
재귀함수에서 BaseCase는(반복문을 멈추는 조건) 반드시 존재해야하는데, 따라서 위 코드도 사실 조금 더 명확하게 아래와 같이 작성하는 것이 좋다.
<pre><code>func binaryRecursion(_ dec: Int) {
 if dec &gt; 0 {
 binaryRecursion(dec/2)
 print(dec%2, terminator:"")
 } else {
 return
 }
}

let n = Int(readLine()!)!
binaryRecursion(n)</code></pre>
BaseCase는 else문이 될 것이다. 재귀함수는 BaseCase가 없을 경우 무한루프에 빠지기 때문에 반드시 작성해줘야한다.
<h2 id="강의-풀이">강의 풀이</h2>
풀이로직에서 차이가 없기 때문에 파이썬코드만 살펴보겠다.
<h2 id="파이썬-코드">파이썬 코드</h2>
<pre><code>def DFS(x):
 if x==0:
 return
 else:
 DFS(x//2)
 print(x%2, end='')
n=int(input())
DFS(n)</code></pre></div></div>

PS & Algorithm

WooSeok Suh

재귀함수를 이용한 이진수 출력
참고자료: 파이썬 알고리즘 문제풀이
상기 강의 내용을 바탕으로 swift 코드로 바꿔서 요약 정리한 내용입니다.
문제
자연수 n이 주어지면 재귀함수를 활용하여, 이진수의 형태로 출력하는 프로그램을 작성하시오.
입력예제
11
출력예제
1011
내 풀이
func binaryRecursion(_ dec: Int) {
    if dec > 0 {
        binaryRecursion(dec/2)
        print(dec%2, terminator:"")
    }
}
let n = Int(readLine()!)!
binaryRecursion(n)
재귀함수를 활용한 반복구조이다. 스택을 제대로 이해했다면 해당 코드를 이해하는 데 큰 어려움은 없을 것이다. binaryRecursion함수를 간단하게 R이라고 한다면, [R(11), R(5), R(2), R(1), R(0)] 순서로 메모리(스택)에 쌓이게 된다. (R(0)에서 멈추는 이유는 dec가 0보다 같거나 작은 경우는 더이상 스스로를 호출(재귀)하지 않기 때문이다.
스택은 Last In First Out이기 때문에 R(0)부터 작업이 시작되는데, 0인 경우는 if dec > 0 조건을 만족하지 못하여 아무런 추가 작업없이 함수가 종료된다. 그리고 R(1)의 4번째 줄로 돌아가고 호출 당시에 실행하지 못했던 print함수를 실행하고 종료된다. 나머지 R(2) -> R(5) -> R(11)도 같은 로직으로 실행되고 종료된다.
따라서 재귀함수에서는 스스로를 호출하는 위치가 굉장히 중요하다. 예를들면 binaryRecursion(dec/2)보다 print(dec%2)를 먼저 실행하면 원하는 해답인 '1011'이 아니라 '1101'이 호출되기 때문에 의도하지 않은 해답을 얻을 수 있다.
재귀함수에서 BaseCase는(반복문을 멈추는 조건) 반드시 존재해야하는데, 따라서 위 코드도 사실 조금 더 명확하게 아래와 같이 작성하는 것이 좋다.
func binaryRecursion(_ dec: Int) {
    if dec > 0 {
        binaryRecursion(dec/2)
        print(dec%2, terminator:"")
    } else {
        return
    }
}
let n = Int(readLine()!)!
binaryRecursion(n)
BaseCase는 else문이 될 것이다. 재귀함수는 BaseCase가 없을 경우 무한루프에 빠지기 때문에 반드시 작성해줘야한다.
강의 풀이
풀이로직에서 차이가 없기 때문에 파이썬코드만 살펴보겠다.
파이썬 코드
def DFS(x):
    if x==0:
        return
    else:
        DFS(x//2)
        print(x%2, end='')
n=int(input())
DFS(n)

완전탐색 - 재귀함수

댓글