Recursive call (재귀) 함수에 관하여

 

stack

ㅇ 기본적인 틀 ㅇ

A에서 A2 -> A3 -> ... -> An 까지 호출후

An -> An-1 -> ... -> A2 -> A1 순서대로 반환

Stack을 쌓고 회수하는 과정이다. 

 

 재귀함수가 어려운이유

1. 인간의 직관으로 이해해야 하는영역이기 때문에 직관적이라는 장점과 직관적이라는 단점이 존재

2. 기존에 접해보지 않은 반복문이라 익숙하지 않음

예를들어서 기본 반복문과의 차이점을 살펴볼때 1부터 10까지 출력하는 프로그램 작성하였을때

for(int i = 0 ; i < 10 ; i++){

   System.out.println("%d", i);

}

 

위와 같이 단순 반복문을 사용할경우에는 매우 쉽지만

 

public class _Ere{

    // 1부터 10까지 출력한다.
    static void sum(int a){

        if(a==11) return;
        System.out.println(a);
        sum(a+1);

    }

    public static void main(String args[]){

        sum(1);
    }
}

위와 같이 재귀적으로 작성할수도 있다. 이건 약간 이해하기가 쉬워보인다. 그래도 순서가 a->b순서대로 가기 때문이다.

그렇다면 이걸 이런식으로 바꾼다면 어떻게 될까

public class _Ere{

    // 1부터 10까지 출력한다.
    static int sum(int a){

        if(a==1) return 1;
        System.out.println(sum(a-1));
        return a;


    }

    public static void main(String args[]){

        System.out.println(sum(10));
    }
}

먼가 머리가 이해가 갈려다가 이해가 어느순간 멈춘다.

왜냐하면 순서가 A->B인줄 알았는데 A->B로 가다가 갑자기 C로 가기 때문이다. 흐름이 끊긴다.

이는 재귀적으로 생각하는 방법을 애초에 사고해보지 않아서 그렇다. 훈련을 통해 기를수 있다고 믿자. 안되면 외우자.

재귀적 사고는 A->B순서가 아닌 A->B로 갔다가 B->A로 돌아오는 순서로 생각해야한다.

 

 

재귀함수를 쉽게 이해하기 이해하기

 

1. 문제에서 핵심적인것을 함수로 생각후 가장 먼저 하는것은 stack으로 그림을 그리는것이다.

ㅡstackㅡ

l sum(1)  l

l .          l

l ..         l

l ...         l

l sum(7)  l

l sum(8)  l

l sum(9)  l

l sum(10) l

ㅡㅡㅡㅡㅡ

 

2. 그리고 stack의 최상단부터 실행이 된다고 생각해야한다.

( ※ 항상 stack이 전부 완성된 마지막을 기준으로 먼저 생각해야한다.)

 

3. stack 에서 pop을 하면서 옆에 있는 기능들이 실행된다고 생각해야한다.

 

ㅡstackㅡ          ㅡfunc()ㅡ

l sum(1)  l           print

l .          l           print

l ..         l           print

l ...         l           print

l sum(7)  l           print

l sum(8)  l           print

l sum(9)  l           print

l sum(10) l           print

ㅡㅡㅡㅡㅡ    

 

4. if문으로 어디까지 stack을 쌓을것인지 명시해줘야한다.

5. 점화식은 그대로 return 문에 적으면 생각할필요없다.(외우자. 외우는게 훨씬 편하다.)

6. 재귀적 사고는 A->B순서가 아닌 A->B로 갔다가 B->A로 돌아오는 순서로 생각

 

1. stack

2. 마지막 생각

3. 기능과 묶어서 생각

4. if문으로 언제까지 쌓을것인지 명시

5. 점화식은 그냥 return문으로( A(n) = A(n-2) + A(n-1) <=> return fibo(n-2) + fibo(n-1) <=> 피보나치수열)

6. A->B로 갔다가 B->A로 돌아오는 순서로 생각

 

위의 6가지를 중점으로 생각의 지도를 펼쳐나가야한다. 기존에 생각대로 이해하려고 하면 이해가 잘 가지 않을것이다.

 

1. stack

fibo(1)

fibo(2)

fibo(3)

fibo(4)

fibo(5)

 

2. 마지막 생각, if문으로 언제까지 쌓을것인지 명시

if n==1 일때 0

if n==2 일때 1

 

3. 점화식외우기

a(n) = a(n-2) + a(n-1)

그대로 return 에 넣기

return fibo(n-2) + fibo(n-1);

public class _Ere{

    // 1부터 10까지 출력한다.
    static int fibo(int n){

        if(n==1) return 0;
        if(n==2) return 1;
        return fibo(n-2) + fibo(n-1);


    }

    public static void main(String args[]){

        System.out.println(fibo(21)); //10개 
    }
}

이런식으로 하여도 어렵기는 하다. 하지만 지속적으로 연습을 한다면 머리가 딱 트이는날이 온다. 본인도 아직까지는 어렵다. 재귀적사고란 원래 어려운것이다 라고 생각하고 여유를 가지고 생각하자.

재귀함수가 쉽다는사람은 머리가 좋거나 오랫동안 해온사람들이다. 쫄거없다.

우리들 놀시간에 저것만 했는데 못하면 바보다. 우리도 할수있다.