안선생의 개발 블로그
재귀 함수 본문
재귀 함수는 함수가 자기 함수를 호출하는것을 재귀 함수라고 한다.
이 재귀 함수에는 종료할 수 있는 기본 조건이 있어야 한다. 그러치 않으면 계속 자기 자신을 호출하면서 무한루프에 빠지게 된다.
예;
꼬리 재귀
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include<iostream>
using namespace std;
void fun(int n)
{
if (n > 0)
{
cout << (n);
fun(n - 1);
}
}
int main()
{
int x = 3;
fun(x);
return 0;
}
|
cs |
이 코드를 예로 들어 본다면 메인 함수를 먼저 시작하고 , 변수 x에 3를 넣고 fun함수를 호출할 것이다 그때 매개변수의 값을 3을 가질 것이다. 그리고 조건문으로 n은 3이므로 0보다 커서 조건문이 실행 될것을 알 수 있다. 먼저 n의값인 3을 출력 할것이다. 그다음에 fun(2)로 자기 자신을 한번 더 호출 한다. 매개변수 2를 갖는 fun함수는 조건문에 걸리므로 2를 출력하고 그다음도 마찬가지로 1을 출력 후 결국 0이랑 같아지면서 if문은 실행이 안되고 함수는 종료될것이다. 그리고 fun(0)부터 거꾸로 올라가면서 실행 할 것이다. 하지만 이미 출력은 다 했기때문에 아무것도 안하고 fun(3)까지 돌아가고 함수는 종료 될것이다. 최종적으로 이 코드의 실행값은 321이 출력될것이다. (오름차순)
다음 예를 보자
헤드 재귀
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include<iostream>
using namespace std;
void fun(int n)
{
if (n > 0)
{
fun(n - 1); cout << (n);
}
}
int main()
{
int x = 3;
fun(x);
return 0;
}
|
cs |
|
|
이번예는 위에 코드랑 비슷한데 출력 위치가 바뀌었다. 위에랑 마찬가지로 3보다 크므로 조건문에 걸린다. fun(2)가 되고 출력문은 수행되지 않는다. 그 이유는 출력문까지 내려가지 않고 함수를 계속 호출하기 때문에 함수의 호출이 완료되어야만 하기 떄문이다. 따라서 fun(2)를 호출하고 조건문에 걸리면 fun(1)에 함수를 호출하게 됩니다. 조건문이 거짓일떄까지 계속하며 함수를 호출한다. 함수 호출이 완료되면 함수를 뒤에서부터 실행한다 즉 내림차순 fun(0)부터 실행하여 출력을 하게된다 fun(3)까지 즉 이 것에 출력은 123이 될것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include<iostream>
using namespace std;
void fun(int n)
{
if (n > 0)
{
//호출할 떄 실행
fun(n - 1);
// 반환할떄 실행
}
}
int main()
{
int x = 3;
fun(x);
return 0;
}
|
cs |
즉 함수를 어디에다 쓰냐에 재귀함수의 값이 완전히 달라질 수 있다. 함수 위에다 쓰면 오름차순으로 실행될 것이고 함수아래에다 쓰면 반환할때 즉 내림차순으로 실행된다는것을 알 수 있다. 이 것이 재귀함수에 특징이다.
'알고리즘' 카테고리의 다른 글
| C++ 문자열 Anagram (0) | 2022.10.11 |
|---|---|
| 배열 ADT (0) | 2022.10.09 |
| 하노이 탑 (0) | 2022.10.01 |
| 피보나치 3가지 방법 (0) | 2022.09.29 |
| 재귀의 정적변수 (0) | 2022.09.26 |
