자료구조 - 4일차 (재귀함수)

#include<stdio.h>

// ---- 재귀함수 ----
// 재귀 : 원래의 자리로 되돌아가거나 되돌아 오다. 반복, 되풀이.
// 재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수.

void Recursive(int n)
{
if(n == 0)
return 0;

printf("Recursive Function!!\n");
Recursive(n - 1); // return이 실행될 때 호출했던 이 지점으로 복귀. 근데 아래에는 더 실행할 코드가 없음.
}

int main()
{
Recursive(3); // 해당 함수가 끝날 때, 해당 함수를 호출했던 줄로 복귀한다. 상당히 중요한 개념.

return 0;
}

// 종료는 호출의 역순으로

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

int Sum(int n)
{
if (n == 1)
return 1;
else
return n + Sum(n - 1);
}

int main()
{
int num;

printf("입력 : ");
scanf("%d", &num);

printf("출력 : %d\n", Sum(num));

return 0;
}

 

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

//  Q1) 팩토리얼 값을 반환해주는 함수(재귀함수)로 구현해보세요.
// 입력 : 4
// 출력 : 24

 

#include<stdio.h>

int Fac(int num)
{
if (num == 1)
return 1;
else
return num* Fac(num - 1);
}

int main()
{
int num;

printf("입력 : ");
scanf("%d", &num);

printf("출력 : %d\n", Fac(num));
return 0;
}

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

// Q2 ) 피보나치 수열을 구하는 함수(재귀함수)로 구현해보세요.
// 1, 1, 2, 3, 5, 8, 13, 21, 34, ....
// 입력 : 6
// 출력 : 8 (우리가 입력한 번지의 수열값)

#include<stdio.h>

int Fib(int num)
{
if (num == 1 || num == 2)
return 1;
else
return Fib(num - 2) + Fib(num - 1);

}

int main()
{
int num;
printf("입력 : ");
scanf("%d", &num);

printf("출력 : %d\n", Fib(num));
return 0;
}

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

// Q3 ) 하노이 탑을 재귀함수로 구현해보세요. (원반 개수 입력)
// 입력 : 3
// 
//  1
//  2
//  3
//  A B C
// 한 번에 한 개의 원반만 옮길 수 있음
// 숫자가 더 큰 원반이 항상 아래에 위치해야 한다.

// 1개
// 1->C

// 2개 3회
// 1->B
// ----
// 2->C
// ----
// 1->C

// 3개 (출력의 결과) 7회
// 1->C
// 2->B
// 1->B
// ----
// 3->C
// ----
// 1->A
// 2->C
// 1->C

// 4개 15회 
// 1->B
// 2->C
// 1->C
// 3->B
// 1->A
// 2->B
// 1->B
// -----
// 4->C
// -----
// 1->C
// 2->A
// 1->A
// 3->C
// 1->B
// 2->C
// 1->C

//  a-> 출발지점
// b-> 큰 수를 빼내기 위한 중간지점
// c-> 도착지점

// 첫 번째 : b와 c의 위치를 바꿔, num-1까지의 수를 B에 위치시킴
//  가운데 : num을 C 에 위치시킴
//  세 번째 : 적재된 num-1의 수들을 시작 지점을 B로 하고 C로 옮기는 과정

#include<stdio.h>

void Han(int num, char a, char b, char c)
{
if (num == 1)
printf("%d->%c\n", num, c);
else
{
Han(num - 1, a, c, b);
printf("%d->%c\n", num, c);
Han(num - 1, b, a, c);
}
}

int main()
{
int num;
printf("입력 : ");
scanf("%d", &num);

printf("출력 :\n");
Han(num, 'A', 'B', 'C');

}