[Algorithm] 재귀 함수 기초 1

재귀 함수는 자기 자신을 호출하는 함수이다. 

프로그램 실행 중 재귀 함수를 만나면, 현재 위치를 저장하여 호출할 함수의 주소로 넘어가 함수 내용을 수행한다. 

함수 실행이 끝나면 원래 위치로 복귀해 다음 코드를 수행한다.

무한 루프에 빠지지 않기 위해 종료 조건이 있어야 하고, 코드를 단순화할 수 있다. 무리하게 호출하면 스택 공간을 이용한다는 재귀함수의 특성 때문에 ‘스택 오버플로우’ 가 일어날 수 있다.

1. 1부터 n까지 출력하기

scanf로 n을 입력받은 후, solve(1) 호출, 이후, solve(n+1)을 수행해 n과 a가 같으면 종료 (종료조건)

따라서, 소스코드는 아래와 같이 쓸 수 있다.

2. n부터 1까지 출력하기 (역순)

solve 함수에서 printf와 solve(n+1) 위치만 바꾸어 주면 된다...

3. 두 수 사이의 홀수 출력하기

1부터 n까지 출력하는 소스 코드에서 홀수를 찾아 모두 출력한다.

if(n % 2 != 0) 조건을 사용하면 된다.

4. 팩토리얼 출력하기

n을 입력받아 n!을 출력한다.

예를 들어, n이 5인 경우, 5! = 5 * 4 * 3 * 2 * 1 = 120을 출력한다.

이 경우에는 점화식을 세워야 한다. 1!은 1이 되므로 종료조건을 아래와 같이 설정하며,

아닌 경우에는 아래와 같이 점화식이 도출되도록 Code를 작성한다.

f(5)

= 5 * f(4)

= 5 * 4 * f(3)

= 5 * 4 * 3 * f(2)

= 5 * 4 * 3 * 2 * f(1)

= 5 * 4 * 3 * 2 * 1

= 120

따라서, 여기서의 점화식은 n * f(n-1) 이다.

5. 피보나치 수열

N번째 피보나치 수를 출력한다. 이 경우에도 점화식을 세운다.

피보나치 수열의 기본 규칙은 처음 두 항은 1이고 세 번째 항부터 이전 두 항의 합이 된다. 

즉, 1, 1, 2 다음부터 1+2 가 다음 항이 된다. 그 다음은 2+3=5가 된다.

따라서, 종료조건 if(n==0) return 0, if(n==1) return 1;

점화식은 f(n-1) + f(n-2) 로 세우면 된다.