[Inflearn] 재귀함수 이진수 출력

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 10진수가 입력되면 2진수로 변환해서 출력하라 !

      

      재귀함수로 풀어내기 위해

      몫이 N을 계속 2로 나누는데 N이 0이 되면 return 처리를 해주면서 재귀함수의 끝을 지정한다.

      if(N == 0) return

      

      그렇지 않을 경우 

      n/2 를 재귀함수에 넣어주고

      toBinary(n/2);

      다음 line 에 printf("%d", n%2); 를 해주면 될 것 같다.

11이 입력되었다고 해보자.     

f(11) 부터 f(0) 까지 스택이 쌓일 것이고

f(0)일 때 return 을 시작으로 한 단계씩 아래로 print 가 수행될 것이다.

f(0) -> return

f(1) -> print(1)

f(2) -> print(0)

f(5) -> print(1)

f(11) -> print(1)

 

     이 과정을 모두 수행하고 종료될 것이다.

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void toBinary(int x)
{
    if (x == 0) return;
    else
    {
        toBinary(x / 2);
        printf("%d", x % 2);
    }
}
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n;
 
    scanf("%d", &n);
 
    toBinary(n);
 
    return 0;
}

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;    
 
void D(int x){
    if(x==0) return;
    else{
        D(x/2);
        printf("%d", x%2);
    }
}    
 
int main(){
    freopen("input.txt", "rt", stdin);
    int n;
    scanf("%d", &n);
    D(n);
    return 0;
}

강사님이 꼭 stack을 그려보라고 하셔서 나는 말을 잘 들으니까

다시 그려보려고 한다. 꺌꺌...

11 이 입력되었을 때,

line 19 를 통해 n 이 재귀함수에 입장한다.

입장을 하고 line 10에서 D(5) 로 재귀함수를 다시 입장한다.

D(11) - 10

D(5)

D(11) - 10

D(5) 로 입장하고 line 10 에서 다시 D(2) 로 입장한다.

D(2)

D(5) - 10

D(11) - 10

D(2) 로 입장하고 line 10 에서 다시 D(1) 으로 입장한다.

D(1)

D(2) - 10

D(5) - 10

D(11) - 10

D(1) 로 입장하고 line 10 에서 다시 D(0) 으로 입장한다.

D(0) - 8

D(1) - 10

D(2) - 10

D(5) - 10

D(11) - 10

D(0) 에서는 종료조건을 만족하게 되고 return 을 수행하면서 

stack 에서 하나씩 넣어둔 함수를 꺼낸다.

먼저 D(1) 을 꺼내면 다음 line 11 문장이 수행되면서

"1" 이 출력된다.

출력까지 다 하면 line 13에서 함수가 종료되므로 스택에서 제거해준다.

D(2) - 10

D(5) - 10

D(11) - 10

다음으로 D(2) 을 꺼내면 다음 line 11 문장이 수행되면서

"0" 이 출력된다.

출력까지 다 하면 line 13에서 함수가 종료되므로 스택에서 제거해준다.

D(5) - 10

D(11) - 10

다음으로 D(5) 을 꺼내면 다음 line 11 문장이 수행되면서

"1" 이 출력된다.

출력까지 다 하면 line 13에서 함수가 종료되므로 스택에서 제거해준다.

D(11) - 10

마지막으로 D(11) 을 꺼내면 다음 line 11 문장이 수행되면서

"1" 이 출력된다.

출력까지 다 하면 line 13에서 함수가 종료되므로 스택에서 제거해준다.

이제 stack 에 있는 모든 함수가 제거되었고 

stack 이 비어있다면 main 함수로 다시 이동한다.

이렇게 stack 을 그려보며 과정을 진행해보았다.

#. Result

  - Input --------------------------------------------------------

11

------------------------------------------------------------------

  - Output --------------------------------------------------------

1011

------------------------------------------------------------------