재귀의 이해

 재귀호출은 함수가 완료되기 이전에 자기자신을다시 호출하는 것이다.

 

 재귀알고리즘을 사용하려면 탈출 조건이 성립해야 한다.

 재귀는 트리구조이고 트리구조는 스택으로 되어있다

 즉 먼저 호출된 재귀가 나중에 탈출하고 가장 마지막에 호출된 재귀함수부터 진행이 된다.

 구조상으로

 함수호출1 --> 함수호출2 --> 함수호출3 --> 함수호출4 --> 함수호출5 --> 함수호출6 --> 종료조건

--> 함수탈출6 --> 함수탈출5 --> 함수탈출4 --> 함수탈출3 --> 함수탈출2 --> 함수탈출1 --> 프로그램종료

 

스택 구조인 것이 이해되는가?

트리를 이야기 한 것은 최상위 노드(첫 재귀호출)부터 반복적으로 재귀호출이 되면서 위에서 아래단계로 함수호출이 이루어진다.

단순 재귀일 경우 선형으로 보이지만 재귀 안에 재귀가 두 개일 경우 분기를 가지게 되어 트리 구조를 이루게 된다 

Ex)

Int Fibo(int n)

{

           If(n == 1 )

             return 0;

          else if ( n == 1 )

             return 1;

       else

         return Fibo(n-1) + Fibo(n-2);     // Tree 구조 처럼 함수호출이 진행 된다.

}

 

재귀 구조를 사용하려면 두 번째 시도 이후부터는 탐색 대상을 찾을 때까지 동일한 패턴을 반복한다.

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

동일한 패턴을 반복한다... 이 말이 중요한 것 같다.. 재귀는 직접 코드를 짜보면서 이해하자..