주뇽's 저장소
Recursion 1-1 ( 순환, 재귀) 본문
# 모든 코드는 C++로 작성되었습니다
Recursion : 프로그램에서 어떤 함수에서 직접적으로 혹은 간접적으로 자기 자신 함수를 호출하는 것
Recursion 은 정의에서처럼 자기 자신을 다시 호출하는 함수이다. 아래와 같이 함수안에서 다시 자기 자신을 호출하는것을 recursion이라고 부른다.
#include <iostream>
void func()
{
func();
} //recursion 함수
int main(){
func();
return 0;
} //main
과연 결과가 어떻게 될까 ? 일단 출력값이 없으니 상황을 잘 모르겠다. 함수가 호출될 때 마다 호출되고있는것을 눈으로 볼 수 있게 출력문을 하나 만들어보았다.
#include <iostream>
using namespace std;
void func()
{
cout << "Hi i am a func " <<" " ;
func();
} //recursion 함수
int main(){
func();
return 0;
} //main
사진과 같이 Hi i am a func 을 미친듯이 출력하는 모습을 볼 수 있다. ctrl + c 을 눌러서 중단해주자
그렇다면 recursion을 어떻게 사용해야 하는걸까 ?
우리가 recursion을 사용하기 위해서는 적절한 구조를 설계 해야한다 다음코드를 한번 보자
#include <iostream>
using namespace std;
void func(int n)
{
if(n<=0){ return ; } // if문 들어온 정수 n이 0보다 작거나 같으면 0을 return
else{
cout << "Hi i am a "<< n << " func" << endl; // 확인을 위한 출력
func(n-1);
}// else문 0보다 크다면 n의 값을 -1하고 그 값을 다시 func함수의 인자로
} //recursion 함수
int main(){
func(5);
return 0;
} //main
제일 처음 func() 함수의 인자값으로 5를 줬기 때문에 (n = 5) n >0 이 성립하므로 else문으로 넘어간다
그리고 나서 Hi i am a 5(n의 값) func 를 출력하고 나서 여기서 n-1의 값인 4를 다시 함수의 인자로 넣어준다
func(4) 호출 -> Hi i am a 4(n의 값) func 출력 n-1을 다시 함수의 인자로
func(3) 호출 -> Hi i am a 3(n의 값) func 출력 n-1을 다시 함수의 인자로
func(2) 호출 -> Hi i am a 2(n의 값) func 출력 n-1을 다시 함수의 인자로
func(1) 호출 -> Hi i am a 1(n의 값) func 출력 n-1을 다시 함수의 인자로
func(0) 호출 -> 이 경우 n의 값이 0이 되므로 if문으로 넘어가서 return ;을 실행 바로 func 함수를 종료시킨다.
# 여기서 만약 func(n-1)이 아닌 func(n+1)로 한다면 어떻게 될까 ?
--> 이 또한 무한루프에 빠지게된다.
이 처럼 우리가 recursion 함수를 사용하기 위해서는 함수가 무한 루프에 빠지지 않게 하기위한 구조를 설계하는것이 중요하다.!
올바른 Recursion 함수를 사용하기 위해서는 두 가지가 필요하다
- 첫 번째로는 적어도 하나의 무한루프에 빠지지 않게해주는 종료조건이 필요하다
- 두 번째로는 결국 Recursion함수를 반복적으로 수행하면서 종료조건으로 가게 만들어야 한다.
1. 먼저 무한루프에 빠지지 않게해주는 조건 !! 이걸 우리는 Base case 라고 부른다 recursion 함수 없이 스스로 계산을 할 수 있는 경우이며 나는 base case를 종료조건이라고 부르겠다 이 조건을 제대로 설정하지 못한다면 처음에서 본것과 같이 함수는 종료되지 못한채로 계속 반복만 할 뿐이다.
2. 그 다음은 적절한 반복함수를 만드는것이다 이 단계를 Recursive step 또는 Recursive case라고 부른다 종료조건을 잘 만들어도 종료조건으로 향하는 방향을 잘못 설정한다면 이 또한 무한루프에 빠진다.
그렇다면 이 두가지를 잘 이용해서 가장 간단한 0 부터 n 까지의 합을 계산하는 add 함수와 가장 기본적인 factorial 함수를 구현해 보자
-Add 함수-
#include <iostream>
using namespace std;
int func_Add(int n) // n은 0이상의 정수
{
if(n==0){return 0;} // base case (종료 조건)
else{
return n+ func_Add(n-1); // recursive step
}
}
int main(){
cout << " func_Add : " << func_Add(3) << endl;
return 0;
}0부터 n까지의 합을 계산하는 함수를 구현해 봤다. 이 코드를 실행하면 어떻게 나오는지 확인해 보면
사진과 같이 0부터 3까지의 합인 6이 잘 나오는것을 확인 할 수 있다.
코드를 하나하나 해석해보자면
# n의 값은 0 이상의 정수
1. base case(종료조건)
- n 의 값이 0이라면 0을 return
2. recursive step : n이 0보다 크다면
- n의 값이 0보다 크기 때문에 입력값 n = 3을 func_Add()함수의 인자로 넣는다 (편하게 func라고 하겠음)
- func(3) -> (n= 3) return 3 + func(2) -------->func(3) = 3 + 3 ( func(2) )
- func(2) -> (n= 2) return 2 + func(1) -------->func(2) = 2 + 1 ( func(1) )
- func(1) -> (n= 1) return 1 + func(0) -------->func(1) = 1 + 0
- func(0) -> (n= 0) return 0 --------> func(0) = 0
함수의 호출을 따라가보면 밑에서부터 0 + 1 + 2 + 3 = 6 으로 0 부터 3까지의 합이 잘 계산되는 모습을 볼 수 있다.
-Factorial 함수-
#include <iostream>
using namespace std;
int func_factorial(int n){// n은 0이상의 양의 정수
if(n==0){ // 0!의 값은 1
return 1; // base case
}
else{
return n*func_factorial(n-1); //recursive case
}
}
int main(){
cout << "func_factorial : " << func_factorial(3) << endl;
return 0;
}위 코드를 실행하고 결과를 한 번 확인 해보자
사진과 같이 3!의 값인 6이 잘 출력되는 모습을 볼 수있었다 !!
이번 함수도 하나하나 해석해보면
# n의 값은 0 이상의 정수
1. base case(종료조건)
- n 의 값이 0이라면 1을 return # 0!의 값은 1이기 때문
2. recursive step : n이 0보다 크다면
- n의 값이 0보다 크기 때문에 입력값 n = 3을 func_factorial()함수의 인자로 넣는다 ( 편하게 func라고 하겠음)
- func(3) -> (n= 3) return 3 * func(2) -------->func(3) = 3 * 2 ( func (2) )
- func(2) -> (n= 2) return 2 * func(1) -------->func(2) = 2 * 1 ( func(1) )
- func(1) -> (n= 1) return 1 * func(0) -------->func(1) = 1 * 1
- func(0) -> (n= 0) return 1 --------> func(0) = 1
이번 문제또한 함수의 호출을 따라가보면 3! = 1 * 1 * 2 * 3 으로 6 이 잘 나오는걸 확인 할 수 있었다.
또한 Recursive 에는 세 가지 유형이 존재한다.
- Unary recursion
- 자기 자신을 호출하는 부분이 한 부분일 때
- example : factorial, linear sum, reversing array...
- Binary recursion
- 자기 자신을 호출하는 부분이 두 부분일 때
- example : Fibonacci numbers, Hanoi tower, merge sorting, quick sorting
- Multiple recursion
- 자기 자신을 호출하는 부분이 세 부분 이상일 때
- example : flood fill, knight's tour
이번 예제들은 모두 자기 자신을 호출하는 부분이 한 부분인 Unary recursion 이다 Unary recursion에 경우에는 굳이 재귀함수를 사용하지 않고 for문으로 구현해도 좋지만 recursive한 사고를 기르기 위해서 재귀함수로 구현해보는 연습을 해보자!!
마지막으로 재귀함수의 몇가지 예제를 더 보고 마무리 해야겠다!
- Fibonacci 함수 -
#include <iostream>
using namespace std;
int func_fibonacci(int n){// n은 0이상의 양의 정수
if(n<=1){ // 0 = 0 , 1 = 1
return n; //base case
}
else{
return func_fibonacci(n-1) + func_fibonacci (n -2); // recursive step (Binary recursion)
}
}
int main(){
cout << "func_fibonacci : " << func_fibonacci(4) << endl;
return 0;
}위 코드를 실행하고 결과를 한 번 확인 해보자
fibonacci의 경우는 Bainary recursion 이다 return 값을 잘 보면 자기 자신을 두 번 호출하는 모습을 볼 수있다.
이해를 돕기 위해 그림을 한 장 준비했다.
위 그림을 보면서 함수의 호출을 한 번 따라가보자 그렇다면 조금은 recursive 함수를 이해하는데 도움이 될 것이다.
마지막으로 Euclid 함수이다!
- Euclid 함수 -
#include <iostream>
using namespace std;
// m > n 보다 커야 한다.
int func_Euclid(int m, int n){
if(m<n){
int tmp = m;
m = n;
n = tmp;
} // 만약 n이 더 큰 경우 m ,n 의 값을 swap
if(m%n==0){
return n;
}
else{
return func_Euclid(n , m%n);
}
}
int main(){
cout << "func_Euclid : " << func_Euclid(25,30) << endl;
return 0;
}
위와 같이 잘 나오는 것을 확인 할 수 있다!!
Recursion이 항상 좋지는 않다
반복문으로 간단하게 표현이 가능하다면 반복문이 더 효율적인 코드가 될 수 있다.
하지만 Recursion 에 익숙해진다면 반복문으로 구현하기 힘든 복잡한 코드도 쉽게 구현할 수 있다.
물론 나는 아직 아니다.. Recursion 넘 어렵 응애
## 추가설명은 다음 시간에 ..##
'알고리즘 > 재귀' 카테고리의 다른 글
| 치킨 배달 (골드 5) [Class 4] (0) | 2024.04.05 |
|---|---|
| 색종이 만들기 (실버 2) [Class 3] (0) | 2024.04.05 |
| Recursion 1-2 (0) | 2021.10.14 |
