Intro
- 멘탈을 정상화 시키고 다시 하나씩 해보려고 합니다!
- 제 나름의 정해진 순서대로 공부를 하고있지만, 결국 하고싶은 순서대로 할 예정입니다. 그리고, 문제에 필요한 지식들을 그때 그때 찾아가면서 좀 야생적으로 공부할 생각입니다.
- 그래도, 필수적인 개념정리는 매일 1개씩 업로드할 예정입니다!
어떤 문제를 보고, "아 이걸로 풀어야겠다!" 라고 생각하는 과정도 중요하기 때문에, 테마를 정해놓고, 푸는 연습은 지양하는 편입니다. 그쪽으로 생각이 굳어버려서..!
오늘은 재귀함수와 순열입니다.
재귀함수
Recursion이라고 부르는 컴퓨터공학에서 "잘" 다루기가 상당히 까다로운 함수의 형태 중 하나입니다. 똑같은 로직을 매개변수만 달리해서 부르는 방법이라고도 합니다. 자기자신을 함수 안에서 호출하는 형태입니다. 여기서 포인트는 로직의 재사용 입니다.
예를들어 봅시다. 5,4,3,2,1,0 땡 ! 하는 카운트 다운이 있다고 생각해봅시다. 아래처럼 짤 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void counter(int num)
{
if (num == 0)
{
cout << "END" << '\n';
}
cout << num << '\n';
counter(num - 1);
}
int main()
{
counter(5);
return 0;
}
재귀함수는 2가지의 큰 특징이 있습니다. 1.종료조건 , 2. 자기자신을 호출하는 부분이 필수적으로 나타나게 됩니다. 이때, 종료조건을 잘 설정해주지 못하면 무한루프에 빠질 수 있으므로 종료조건을 필수적으로 정해주어야 합니다.
재귀함수의 장점 , 반복문보다 뛰어난게 뭔데?
재귀함수로 짤 수 있는 로직은 반복문으로 짤 수 있습니다. 위의 타이머도 아래와 같이 반복문을 이용할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int counter = 5;
while (counter >= 0)
{
cout << counter << '\n';
if (counter == 0)
{
cout << "END" << '\n';
break;
}
counter--;
}
return 0;
}두 코드를 비교해서 보면, 똑같은 동작을 하게 되지만 가독성과 내부처리에서 차이를 보이고 있습니다.
- 재귀함수는 함수의 로직이 겉으로 잘 드러납니다.
- 재귀함수는 반복문보다 코드의 길이가 짧습니다.
- 재귀함수는 스택 메모리를 사용합니다.
하지만, 반복문을 이용한 코드도 함수로 뺀다면 가독성을 충분히 확보할 수 있습니다. 그러므로, 대부분의 상황에서는 취향차이라고 할 수 있지만 재귀로 구현했을 때 유리한 경우가 종종 있습니다.
재귀와 반복문의 결론
결국 , 자신이 잘하는 방법으로 구현을 하는것이 좋습니다. 최악은 구현을 못하는거니까요. 어떤 방법이든 자신에게 잘 맞는걸 하고, 부족한 부분을 채워야합니다. 저는 반복문으로 구현을 자주합니다만, 종종 재귀를 섞어서 쓰려고 노력합니다. (shark는 재귀가 약한 편이기 때문에)
재귀의 예시
재귀의 예시로 단골손님들이 많습니다. 피보나치수열, DFS, 팩토리얼,순열 등이 있습니다.
재귀로 표현하기 유리한 경우는 제가 느끼기에는 아래와 같습니다.
- 자기 자신을 재사용하는 경우
- 매개변수의 변화가 크지않은 경우
간단하게 피보나치를 재귀적으로 구현해보겠습니다. 피보나치의 정의는 아래와 같습니다.
#include<bits/stdc++.h>
using namespace std;
int Fibo(int n){
if ( n== 1 || n==2 ){
return 1;
}
return Fibo(n-2) + Fibo(n-1);
}
int main(){
int res= 0;
res = Fibo(5);
cout << res << '\n';
return 0;
}다음 글은 순열과 조합에 대해서 다루어볼 예정입니다.
