Algorithm 재귀함수, 이진재귀

재귀함수가 진행되는 과정은 별로 어렵지 않다. 

원리자체는 쉽지만 조건이 추가되면 어려워진다. 복잡해진다는말이 더 맞겠다.

Algorithm 문제풀이는 어렵다.  DFS, BFS공부를 시작하고나서부터 과연 내가 이해하고 적용하며 적응 할 수있을지 걱정이 된다.

 

하지만, 언제나 그랬듯이 결국엔 잘하게 될 나를 믿는다.

무언가를 처음시작할 때마다,

걱정이 무색하게도 처음과 끝의 나는 달라져있었고, 

꽤나 만족스러운 끝을 경험할 수 있었던 것은

시작의 무게를 버텨냈기 때문이다.

그러니까 쫄지말고 끝까지 하면된다. 공부든, 취업이든, 운동이든, 일이든, 뭐든.

쫄지말고, 그냥, 할일을 하자. 그날 그날, 순간 순간을 버티자. 

 

 

 

 재귀함수 

       :    재귀함수는 끝 날때까지, 자기 자신을 반복하여 호출한다.

 

반복문의 역할을 하는 함수(메서드) 라고 생각하면 되는데, for문이나 while문이 계속 자기자신의 처음으로 돌아가서 반복하는것처럼 재귀함수도 자기자신을 계속 반복하며 돈다. 언제까지? "호출이 끝!!" 이 선언될 때까지.

 

아래의 로직을 보자. main메서드에서 recursion메서드를 호출했다. recursion메서드 안에는 자기자신을 호출하는 코드가 있어서 recursion(n-1)는 끝없이 1씩 작은 수를 담아서 자기 자신을 호출할 것이다.

아래 로직에는 호출끝 선언이없다. 그래서 무한루프에 빠진다.

public int recursion(int n){
	recursion(n-1); //자기자신호출
}

public static void main(String args[]){
	recursion(100); //첫호출
}

 

재귀함수에서 중요한 것은 stack프레임을 사용한다는 것이다.

아래의 소스를 보자. 

 

recursion메서드에 출력문 두개가 있다.

잘 보면 동일한 데이터 n을 출력하는데도, 출력되는 값이 다른것을 볼 수 있다. 

 

why? -  recursion메서드 호출문의 앞이냐 뒤냐에 따라 달라진다. (stack프레임을 사용한다는말에서 정답의 힌트를 얻을 수 있겠쥬?)

public int recursion(int n){
    if(n==1) return;

    System.out.println(n);  //100  99  98  97  ...  3  2  1
    recursion(n-1);  //자기자신호출
    System.out.println(n);  //1  2  3  4  ...  98  99  100
}

public static void main(String args[]){
    recursion(100); //첫호출
}

 

stack과의 상관성을 알아보기 전에 다시 한번정리해보자.

 

재귀함수는 자기자신을 반복호출한다. recursion(n-1); 그렇기에 자기자신을 호출하는문장의 뒷 문장은 실행되지 않는다.

끝까지 실행이 안되는 것은 아니고,

반복호출이 끝날때! 위 코드를 기준으로  'n이 1이 될 때' 반복호출은 끝나고 다음문장이 실행되는것이다.

 

그런데 왜 데이터의 순서가 다르게 찍힐까???

앞서 말했듯 재귀함수는 stack프레임을 사용한다. 자료구조 Stack은 나중에들어간게 먼저나오는 후입선출 방식이다. 

재귀함수가 자기자신을 호출할 때마다

stack에는 호출정보가 차곡차곡 쌓인다. 호출할 때의 '매개변수값', '로컬변수값','호출된 위치' 이런 정보가 stack에 쌓이는 것이다. 

 

그리고자기자신 반복호출이 끝나면! 실행되지 못한채 남아있던 로직들이 차근차근 실행된다.

stack이기 때문에 가장 나중에 들어간 데이터부터 하나씩 빠져나오고,

그때 출력문으로 데이터를 찍어보면, stack에 들어갈 때의 데이터와 정반대의 순서로 데이터가 출력되는 것을 볼 수 있다.

 

 

정리

  1. recrusion()함수가 호출될 때의 정보를 stack이 가지고 있다가

  2. 재귀함수의 반복이 끝나면 

  3. 가장 나중에 들어온 데이터부터 하나씩 꺼낸다.

  4. 호출문 다음에있는 문장들을 실행시킨다.

 

 

 

이진재귀 풀이

  문제 : 10진수 N이 입력되면, 2진수로 변경하여 출력하라

import java.util.*;

class Main{
    public static void recrusion(int n){
       if(n==0) return; //n이 0과 같아지면 재귀 끝 !!! (10진수가 2진수로 변경끝)
        recrusion(n/2); //n을 2로 나눈 값을 매개변수로 전달 (stack에 n값을 저장하기위함)
        System.out.print(n%2+" "); //stack에 저장되어있던 n값의 나머지값을 출력한다. 나중에 호출된 n값이 가장 먼저 나오기 때문에 10진수 n이 2진수로 변경된 값이 출력된다.
    }
    public static void main(String args[]){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        recrusion(n);
    }
}

결과 및 자료구조