재귀함수에 대해서 재귀함수와 반복문이라는 글을 짧게 적어놓은게 있습니다.
지금은 재귀에 대한 이해가 저 글을 적을 때보단 깊어진 상태이고, 재귀함수에 대해서 새롭게 안 사실들이 많아서 새롭게 적어보려고 합니다.
재귀
하나의 함수에서 자기 자신을 다시 호출해, 작업을 수행하는 방법입니다. 예를들어, N까지의 합을 구하는 재귀함수를 만들어봅시다.
#include<bits/stdc++.h>
using namespace std;
int add(int n){
if(n==1){
return 1;
}
return n+f(n-1)
}
int main(){
return 0;
}재귀함수와 For문
Shark 본인은 재귀함수로 구현할 수 있는 케이스의 대부분은 For문으로도 대체가 가능하다고 생각하고 있습니다. 실제로 For문으로 작성하던, 재귀함수를 이용해서 작성하든 구현에서 차이는 있지만, 결과물은 똑같게 나옵니다. 그래서, 저는 웬만하면 For문을 이용해서 작성을 합니다. 저에게 For문이 더 직관적으로 다가오기 때문이죠.
하지만, 재귀로 구현하는게 유리한 경우는 분명이 있습니다. 대표적으로, 하노이 탑 문제가 있습니다. 하노이 탑을 For문으로 이용하게 된다면 반복하는 횟수를 정해야하는데, 상당히 까다롭게 될 겁니다.
왜 재귀로 구현하면 유리한 경우가 생길까요?
그건, 절차지향적으로 생각하면 복잡해지는 경우가 있기 때문입니다. 예를들어, Combination(조합)을 절차지향적으로 생각을 해봅시다. N명 중 R명을 뽑는다고 생각해봅시다.
절차지향적인 생각(Step By Step)
1명을 뽑고 -> 남은 애들 중에서 또 한명을 뽑고 -> 또 남은 애들 중에서 1명을 뽑고 -> .....R명이 될때 까지 뽑는다.
for(int i=0;i<N;i++){
//한명을 뽑았다.
for(int j=i+1;j<N;j++){
//남은 친구에서 뽑는다.
for(int k=j+1;k<N;k++){
//남은 친구에서 뽑는다.
... R개의 반복문이 필요함.
}
}
}Step By Step으로 생각하는 것은 프로그래밍에서 정말 소중하면서 중요한 개념이지만, 때로는 Step By Step으로 했을 때, 위처럼 복잡해지는 상황이 오게 됩니다. R개의 반복문이 정해져있다면 몰라도, 상황에 맞게 반복문을 생성하는 것은 불가능합니다.
특정 N번 반복을 해야하는데, 매번 반복하는 반복문의 갯수가 특정 조건에 따라서 유동적이어야 한다면, 재귀함수가 유리할 수 있습니다. 위의 조합에서는 R개의 반복문이 필요하기 때문에, R 또한 '변수'의 개념이 되어버립니다.
재귀의 숨은 의미
저는 반복문으로 먼저 생각을 해본 뒤, 반복문이 유동적으로 필요한 것을 본다면 재귀가 유리할거라 판단을 합니다 혹은, 저의 좁디좁은 경험을 비추어서 판단을 합니다. 일종의 소거법/경험적인 지식을 이용하는거죠! 하지만, 재귀의 의미를 이해하게 된다면, 소거법보다 재귀를 더 잘 이해할 수 있게 됩니다.
재귀함수로 문제를 해결한다는 말은 특정 K번째,K+1번째,....N번째까지 만족하는 로직을 짜겠다. 즉 , 문제를 귀납적으로 풀겠다는 말과 일치하게 됩니다. 우리는 알게 모르게, 귀납논증을 프로그래밍 적으로 하고 있는거죠!
귀납적으로 문제를 해결하려면, F(1)을 정의해주고, F(K)가 참일 때, F(K+1)또한 참임을 보여주면 됩니다. 혹은, F(K-1) 이 참일 때, F(K)가 참임을 보여줘도 됩니다.
F(1)을 보여주는 이유는 , F(K)가 참일 때, F(K+1)이 참인 케이스에 F(1)은 들어가지 않기 때문에, 따로 증명이 필요하기 때문입니다.
이걸 프로그래밍의 구현 관점에서 보자면 아래와 같이 됩니다.
- F(1)을 정의한다 ==> 내가 정의할 재귀함수의 BaseCondition을 정의한다.(종료할 조건을 정의한다)
- F(K)가 참일때, F(K+1) 또한 참이다 ==> K번째 결과가 K+1번째에도 이용이 된다. 즉, 이전 로직이 다음 로직에도 쓰인다.
재귀함수가 "로직"을 짜는게 중요한 이유이고, 로직이 명확하게 드러나는 이유이기도 합니다. 또, 재귀함수로 문제를 풀 수 있는 이유기도 하고요. 하지만, 내부 실행과정(실제로 호출되는 과정)은 복잡하게 되고, 함수호출이라는 다소 for 반복보다는 무거운 작업을 하게됩니다.
재귀함수의 설계
- 재귀함수 설계를 할 때는 어떤 상태를 가지고, 어떤 값을 나에게 다시 돌려줄 것인지 명확하게 정의를 해야합니다.
- 몇 개의 인자를 가지는게 문제상황을 나타낼 수 있는지 명확하게 정의를 해야합니다.
- 재귀함수는 언젠가는 종료되어야 합니다. 종료하는 조건을 명확하게 해야합니다.
즉, 매개변수와 내부 로직을 신경쓰면서 종료할 조건을 잘 정해주라는 이야기입니다. 예를들어, 위의 조합 예시는n명 중 R명를 뽑습니다.
- 내가 현재 몇명까지 뽑았는지
- n명이 몇명인지
- R이 몇인지를 알아야합니다.
몇명까지 뽑았는지는 함수를 직접 실행하면서 바뀌는 값이기 때문에, 매개변수로 가지는게 좋을 것 같습니다. n명은 전역변수로 취급해도 상관없을 것 같습니다. R또한 전역변수로 취급해도 상관없을것입니다. 따라서 void Combi(int start) 이런 형식으로 짜거나, void combi(int n,int r, int depth)와 같이 3개를 다 받는 함수로 짜도 상관은 없습니다.
출처
