2장 재귀 - 재귀에 대한 이해와 활용 -

* 함수의 이해를 알자.

  함수의 이해는 보통 호출관계 + 호출 순서로 이해가 되는데

  재귀함수에서는 호출 순서를 따지고 들면 너무 복잡해지고, 힘들며, 이득도 없다.

  무슨 말이냐하면, 수식을 만들고 그에 따라 만든 코드가 출력을 통해 잘 나오는 것을 

 확인 했으면 증명에 들어가는데 그 증명을 과감히 생략하라는 것이다. 

 * 재귀적 사고

  수학 -> 재귀식 -> 코드 -> 출력 된 값과 예상 답 확인

  그러나 수학식을 구하기는 정말 어렵기 때문에 재귀식을 논리적으로 구현할 수 있다면

 그것으로도 충분하다.

1. 재귀 함수란?

 함수 내에서 자기 자신을 다시 호출하는 함수를 의미한다.

 이 때 함수를 호출하는 것은 복사된 함수를 호출하는 것이다. 즉, 지금 실행하고 있는 함수가 아닌

정의 된 함수를 복사하여 실행되는 것이다. 그것의 이해는 명령문이 CPU로 이동되어-복사되어 

실행이 되는 것을 통해 알 수 있다.

 2. 재귀함수의 대표적 예.

  팩토리얼은 그 대표적인 예가 된다. 

  < 수식 >

  f(n) = n * f(n-1) ... n >= 1

           1            ... n=0

  < 코드 >

  int Factorial(int n) { 

if(n == 0)

return 1;

else

return n * Factorial(n-1);

  }

  3. 재귀의 활용 - 피보나치 수열

   전전수와 전수를 더하면 다음 수가 나오는 것을 피보나치 수열Fibonacci Sequence라고 한다.

 

  < 수식 >

   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ....

   fib(n) = 0 ... n = 1

              1 ... n = 2

              fib(n-1) + fib(n-2) ... 수식을 반환

  < 코드 >

  int Fibo(int n) {

if(n==1)

return 0;

else if(n==2)

return 1;

else

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

  }

  

 4. 이진 탐색 알고리즘의 재귀적 표현

  논리 자체가 재귀적이라면, 재귀적 표현이 가능하다. 즉, 이진 탐색의 경우 탐색 대상을 찾을 때까지

 동일한 행위가 반복 되기 때문에 가능한 것이다.

 그것을 다음과 같이 표현 할 수 있다.

 1) 탐색 범위의 중앙에 목표 값이 저장되었는지 확인한다.

 2) 저장되지 않았다면 탐색 범위를 반으로 줄여서 탐색을 다시 시작한다.

int BSearchRecur(int ar[], int first, int last, int target)
{
	int mid;
	if(first > last)
		return -1;    // -1의 반환은 탐색의 실패를 의미
	mid = (first+last) / 2;    // 탐색대상의 중앙을 찾는다.

	if(ar[mid] == target)
		return mid;    // 검색된 타겟의 인덱스 값 반환
	else if(target < ar[mid])
		return BSearchRecur(ar, first, mid-1, target);
	else
		return BSearchRecur(ar, mid+1, last, target);
}

어떤 재귀적 수식이던 탈출 조건이 있어야지만, 탈출 할 수가 있는데, 4번째 라인의 if문이 그것이고,

6~9라인이 1)번 나머지가 2)번에 해당된다.