F#에서는 recursive function이 while과 for과 같은 loop을 대체 한다고 하셨다.
예전에 강의했을 때 누군가가 recursive function을 사용하는 것과 loop을 사용하는 것의 차이를 물어봤던 게 어렴풋이 생각났다.
내가 제시한 코드가 loop으로도 할 수 있는 거였는데 굳이 recursive function을 써야 하는지 같은 거였다.
나는 함수에서 recursive 하게 한 번 호출하는 건 loop으로 바꿀 수 있고, 지금이 그런 경우지만, 예를 들어 merge sort처럼 recursive 한 호출을 두 번 이상 해야 하는 경우는 loop으로 해결할 수 없다는 식으로 대답했던 거 같았다.
그러다가 봄 초급 divide & conquer 강의할 때 맨 마지막에 했던 말도 생각났다.
사실 이 알고리즘의 본 의의는 문제를 여러 개로 쪼개는 데에 있는데
이에 반해 그냥 문제의 size만 줄여나가는 경우라고 하면 그건 divide보다는 decrease에 더 가까운 의미이고
그래서 그런 것들은 따로 decrease & conquer라고 부르기도 한다는 거.
이 맥락에서 보면 recursion으로는 divide와 decrease 모두를, loop으로는 decrease만을 처리할 수 있다.
수업 끝나고 예전에 했던 강의 녹화 동영상을 찾아봤다.
https://youtu.be/OvBrH59uOoE?si=dzdwgRkd1dVqLOcs&t=3177
동영상 52:57에
Q: 재귀함수를 통해 해결하는 것과 for 문을 통해 해결하는 것 중 속도는 어느 것이 더 빠른가요?
A: 속도만을 본다면 for 문을 사용하는 게 더 빠를 거다. 재귀함수를 호출할 때마다 지역 변수를 생성하고 등등 추가 작업이 필요하므로 시간이 더 많이 걸릴 거 같다. 그렇지만 재귀함수를 사용하면 함수가 호출될 때마다 parameter는 지역 변수로서 새로 생기기 때문에, callee 함수에서 값이 바뀌는 것이 caller 함수에 영향을 미치지 않는다는 장점이 있다. 그리고 이것은 divide & conquer나 DFS를 구현할 때 많이 사용된다.
(내 기억과는 다르게 둘의 차이를 물은 건 아니었다. 그냥 내가 이걸 대답하면서 loop으로 해결할 수 있는 걸 굳이 recursive function으로 짤 필요가 있을까에 대해 고민해서 그렇게 기억됐나 보다.)
이때 풀던 건 palindrome인지 확인하는 문제였다. 나는 recursive function을 이용한 코드를 짜서 보여줬었다.
bool is_palindrome(const string& s, int left, int right) {
if (left >= right) {
return true;
}
if (s[left] != s[right]) {
return false;
}
return is_palindrome(s, left + 1, right - 1);
}
int main() {
string s; cin >> s;
cout << (is_palindrome(s, 0, s.size() - 1) ? "yes" : "no") << kEndl;
}
이건 decrease 문제이고, 따라서 loop로도 해결할 수 있다.
int main() {
string s; cin >> s;
int l = 0, r = s.length() - 1;
bool is_palindrome = true;
while (l < r) {
if (s[l] != s[r]) {
is_palindrome = false;
break;
}
l++;
r--;
}
cout << (is_palindrome ? "yes" : "no") << kEndl;
}
이에 반해 divide 문제는 재귀함수로 처리하는 것이 깔끔하다.
caller 함수와 callee 함수에 local variable이 별개로 존재하게 되기 때문에.
그리고 위 동영상 59:39쯤에서 하노이 탑 문제를 풀면서 이 이야기를 한다.
void hanoi(int, int, int);
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N;
cin >> N;
cout << (int)pow(2, N) - 1 << '\n';
hanoi(1, 3, N);
return 0;
}
void hanoi(int from, int to, int cnt)
{
if (cnt == 1) {
cout << from << ' ' << to << '\n';
return;
}
hanoi(from, 6 - from - to, cnt - 1);
cout << from << ' ' << to << '\n';
hanoi(6 - from - to, to, cnt - 1);
}(그 당시에 짰던 코드. 지금이랑 스타일이 많이 다르다!)
recursion에는 두 가지 종류가 있다는 걸 깨달았다.
1) recursive call을 하는 것을 마치 subprocess를 반복적으로 생성하는 것과 유사하게 사용 (ex. 위에서 말한 divide)
2) 하나의 process를 계속 반복하기 위함인 경우(ex. 위에서 말한 decrease)
loop은 2번과 유사한 맥락이기 때문에 recursion으로 대체될 수 있다. 그러나 recursion의 1번 내용이 loop으로 대체되진 않는다. 여러 process가 작동하는 것과 유사한 것을, 하나의 process가 작동하는 것으로 대체할 순 없으니까.
ㅎㅎ
수업 듣다가 갑자기 예전 일 생각 난 게 신기하다. 머릿속 한 구석에 아직 옛 기억들이 저장되어 있나 보다.
덕분에 오랜만에 강의한 거 보니까 재밌다. 당시에 긴장해서 목소리 떨리는 거 웃기고 설명한 내용들이 좀 명확하지 않은 것 같아서 부끄러움.
제가 지금 한 이야기도 잘못된 거 있으면 꼭 알려주세요. 표현들이 좀 엄밀하진 않은데, 맥락을 전달하는 데 우선 중점을 두었습니다.
아무튼 재밌어!
+) 추가
깨달아버렸습니다.
지금 생각은 가득한데 말로 정리는 잘 안 되는 상태인 거 같습니다.
지나가던 고수분들 혹시 의견 있으시면 공유해주시면 정말 감사하겠습니다.
https://blog.naver.com/mini_gb/223384354393
F#에서는 recursion이 loop을 대체한다.
F#에서는 recursive function이 while과 for과 같은 loop을 대체 한다고 하셨다. 예전에 강의했을 때 누군...
blog.naver.com