C 로 구현한 알고리즘 - 1부 준비, 3장 재귀

최근에 어떤 계기로 미루고 미뤄왔던 알고리즘 공부를 시작했다.

대학 다닐 때 알고리즘 수업 2번 연속 출석미달로 'F' 받았던터라, 늘 찜찜했는데...

알고리즘을 공부하기 위해 선택한 책은 "C 로 구현한 알고리즘" 이다.

왜냐하면... 나름 오라일리 책인데다가... 회사에 굴러다녀서 살 필요가 없어서...;

대충 1장 소개랑 2장 포인터 다루기는 패스하고

3장 재귀부터 복습 겸 글을 남겨본다.

개본적 재귀(recursion)

문제를 자신보다 점점 더 작은 인스턴스들로 정의할 수 있게 하는 강력한 원리이다.

전산에서는 자신을 호출하는 재귀 함수를 사용해서 재귀적으로 정의된 문제들을 해결한다.

Depth 가 깊어지면 스택 오버플로우의 위험이 크다.

현업에서 실제로 이런 형태를 쓰면 안되겠지.

꼬리 재귀(tail recursion)

컴파일러가 최적의 코드를 만들어 낼 수 있는 재귀의 형태이다.

재귀 호출이 함수 몸체의 제일 마지막에 실행되는 문장이고,

리턴값이 다른식에 사용되지 않는 형태이다.

다시 말해면 재귀함수 호출한 뒤에 수행할 명령이 없어야 한다는거?
(이런 형태는 굳이 Iteration 하게 정의해서 풀 수도 있지만,

 재귀 형태가 머랄까.. 좀 더 문제를 푸는 방법을 명확히 나타내는 듯 하다.

 요새는 컴파일러가 똑똑해져서 최적화 옵션을 주면

 꼬리 재귀도 알아서 Iteration 하게 만들어 준다니깐.. 머.)

팩토리얼 값을 구하기 위한 기본적 재귀와 꼬리 재귀

(빨갛게 표시한 부분을 주목)

따로 부연설명은 하지 않겠다.

기본적 재귀	꼬리 재귀
int fact (int n) {     if (n< 0)         return 0;     else if (n == 0)         return 1;     else if (n == 1)         return 1;     else         return n * fact (n-1); }	int facttail (int n, int a) {     if (n < 0)         return 0;     else if (n == 0)         return 1;    else if (n == 1)         return 1;     else         return facttail (n-1, n*a); }

주의사항

재귀함수는 반드시! 하나 이상의 종료조건이 있어야 하며,

재귀호출이 이 종료조건에 도달할 수 있어야 한다.

그렇지 않다면 스택 오버플로우~

결론

재귀 알고리즘을 모르지는 않았지만,

꼬리 재귀에 대한 좀 더 명확한 이해를 할 수 있었고,

이제 더 정확히 알고 사용할 수 있을꺼 같다.

이상 끝.