재귀 호출

분할 정복

• 문제의 크기 N
• 큰 문제를 작은 문제로 환원
• 작은 문제 역시 큰 문제와 유사함

이진 탐색

BinarySearch(SearchRange)   괄호 안은 탐색범위

{

   if (One Page)   베이스 케이스

      Scan Until Found;

   else

   {

      Unfold the Middle Page;   가운데 펼침

      Determine Which Half;     전반부, 후반부 판단

      if First Half

           BinarySearch(First Half);    전반부 재귀호출

      else BinarySearch(Second Half);   후반부 재귀호출

   }

}

      

문제 크기 감소 : N, N/2, N/4, ... ,1

재귀 호출은 반드시 베이스 케이스에 도달해야 함.

 

재귀적 팩토리얼

n! = n*(n-1)*(n-2)*...*1 (단, 1! = 0! = 1)

int Factorial(int n)

{ if (n==1)

   return 1;

 else 

   return (n*Factorial(n-1));

}

 

문자열 뒤집기1

void Reverse(char S[ ], int Size)

{   if Size(==0)

       return;   호출 함수로 되돌아감 

    else

    {   printf("%c", S[Size-1]);   마지막 문자를 쓰기

        Reverse(S,Size-1);   재귀호출

    }

}

 

재귀함수 작성

Step1

• 더 작은 문제로 표시할 수 있는지 시도
  - 문제 크기를 하나씩 줄이는 방법
  - 반으로 줄이는 방법
  - 다른 여러 개의 작은 문제의 조합으로 표시하는 방법
• 문제 크기 파라미터 N을 확인

Step2

• 문제를 직접 풀 수 있는 것이 어떤 경우인지, 즉, 베이스 케이스를 확인

Step3

• N이 줄어서 반드시 베이스 케이스를 만나는지 확인
• N이 양수인지 음수인지, 짝수인지 혹수인지, 또는 보동소수인지 정수인지 모든 경우에 대해 모두 검증.

Step4

• 베이스 케이스와 베이스 케이스가 아닌 경우를 나누어서 코드를 작성

재귀호출의 효율성

활성화 레코드의 비효율

• 공간적 비효율(저장공간)
• 시간적 비효율(저장, 복원에 걸리는 시간)
• 가능하다면 반복문으로 대치하는 것이 유리

꼬리재귀

재귀호출 명령이 함수 마지막에 위치

• 되돌아올 때 할 일이 없는 재귀호출
• 새로운 활성화 레코드 공간을 만들지 않고 이전 공간 재사용
• return (N*Factorial(N-1)); 는 꼬리재귀 아님
• Factorial(N-1) 결과가 리턴되면 거기에 N을 곱하는 일이 남아 있음.

꼬리 재귀를 사용한 팩토리얼

int Factorial(int n, int a)

{   if (n==0)

       return a;  // a에 결과 값이 축적됨

    else

       return Factorial(n-1, n*a)  //꼬리 재귀   

}