[알고리즘] 단순 반복을 넘어서: 절차적 사고에 재귀를 더하다

도입부 (Introduction) : 재귀적 사고의 필요성

 

여태까지 컴퓨터정보공학을 전공하면서 알고리즘에 대한 공부가 취약했기 때문에 튼튼한 기초를 잡고자 알고리즘의 기초부터 공부하기 시작했습니다. 도중, 재귀 카테고리를 접하면서 프로그래밍을 대하는 사고방식 전환의 필요성을 느꼈습니다. 

평소에 재귀의 개념을 완전 모르지 않고 간단한 팩토리얼 구현 등등 혹은 필요에 의해서 사용하는 수준에서 재귀의 대표격인 하노이의 탑 문제를 접했을 때 어디서 부터 설계를 해야할지 감이 안왔습니다. 이후 작동 원리를 이해한뒤에 코드를 보면 몇 줄이면 해결이 되는 모습을 보고, 코딩을 대하는 사고방식에 공백이 있다는 것을 인지하게 되었습니다.

 

소프트웨어 프로젝트를 다룰때나 평상시에 발생하는 문제에 대해 해결하는 방식이 절차적이고 논리적으로 이를 분석하고 해결방법을 설계해나가는 것을 주 방법으로 사용했습니다. 이 사고에 입각하여 재귀가 필요한 상황에서 문제를 해결하려고 하면 절차를 설계하기 힘들다는 것이였습니다.

 

정확히는 기초 자료구조(링크드 리스트, 스택, 큐 등)와 기초 탐색(DFS, BFS, 이분탐색 등) 및 정렬(버블, 선택, 퀵 등)을 구현함에 있어 절차적 설계 방법으로 큰 이슈를 못느꼈으나 해쉬, 분할정복, 재귀를 접하면서 알고리즈 설계에 한계를 느꼈습니다.

 

이를 해결하기위해 오늘부터 재귀적 사고를 뇌 한편에 자리잡는 연습을 하고자 계획하게 되었으며 이를 위한 필수 개념을 해당 포스트를 통해 작성하게 되었습니다.

 

---

 

알고리즘의 4가지 필수 사고

 

알고리즘은 복잡한 문제를 효율적으로 해결하기 위한 논리적 절차와 규칙의 집합입니다. 효과적인 알고리즘을 설계하기 위해서는 단순히 코드를 작성하는 것을 넘어, 문제를 분석하고 해결하는 사고방식을 이해하는 것이 중요하다고 생각합니다. 프로그래밍에서 주로 활용되는 4가지 핵심 사고방식은 다음과 같습니다:

1. 절차적 사고 (Procedural Thinking)
   문제를 단계별로 나누고 순차적으로 해결하는 기본적인 사고방식입니다. 이는 반복문과 조건문을 통해 데이터를 처리하거나 알고리즘의 논리를 명확히 구현하는 데 사용됩니다.
2. 재귀적 사고 (Recursive Thinking)
   문제를 자기 자신과 비슷한 더 작은 문제로 나누어 해결하는 방식입니다. 기저 조건(Base Case)과 재귀 호출(Recursive Case)을 통해 문제를 단순화하는 데 적합합니다.
3. 분할 정복 사고 (Divide and Conquer Thinking)
   문제를 더 작은 하위 문제로 분할하고 각각 독립적으로 해결한 후, 결과를 결합하여 전체 문제를 해결하는 사고방식입니다. 병합 정렬(Merge Sort)과 같은 고급 알고리즘에 활용됩니다.
4. 최적화 사고 (Optimization Thinking)
   제한된 자원(시간, 공간) 안에서 효율적인 해결책을 찾는 사고방식으로, 동적 프로그래밍(Dynamic Programming)과 그리디 알고리즘(Greedy Algorithm)에서 자주 사용됩니다.

이 중, 절차적 사고와 재귀적 사고는 모든 알고리즘 설계의 기초를 이루며, 분할 정복 사고 (Divide and Conquer Thinking) , 최적화 사고 (Optimization Thinking)로 가기 위한 핵심 사고입니다. 그렇기 때문에 절차적 사고 뿐만 아니라 재귀적 사고의 필요성을 절실하게 느꼈습니다.

---

절차적 사고 (Procedural Thinking)

절차적 사고는 알고리즘 설계의 가장 기본적인 사고방식으로, 단계별로 문제를 해결하는 구조입니다. 현실 중 문제가 발생했을 때 이렇게 하면 이렇게 해결하고 저렇게 하면 저렇게 했다가 저렇게 했고 이렇게 생각을 해보듯이 절차적 사고는 프로세스의 디자인이라고 저는 표현하고 싶습니다. 

 

웹 페이지를 개발한다고 가정했을 때, 로그인 버튼을 누르면 사용자의 아이디, 비밀번호를 검증하고 성공할 경우 권한을 주고, 실패하면 로그인 창으로 리콜하고 이런식으로 설계하는 과정이 절차적 사고에 입각한 설계입니다.

---

재귀적 사고 (Recursive Thinking)

 유트브로 하노이의 탑에 대한 설명하는 영상을 보다가 강의 하시는 분의 한마디가 인상이 깊었습니다.(https://youtu.be/vq7dpFWpwAE?si=bNJeieid_xftz7-A)

" 재귀의 매력은 동작 원리를 깊게 이해하지 않아도 규칙을 파악하고 구현하면 해결된다는 것".

 

기존 알고 있던 재귀적 사고는 "문제를 더 작은 문제로 쪼개어 해결하는 방식이며 이는 함수가 자기 자신을 호출하면서 문제를 해결합니다." 정도 였고 깊게 생각하지 않았기 때문에, 재귀의 역할을 문제를 단계적으로 쪼개서 들어가는 반복분을 직관화 할 수 있는 정도만 인식하고 있었습니다. 

 

하지만 동작원리보다 "규칙"에 포커스를 맞추어 코드를 설계하면 전체 문제가 해결된다는 개념은 절차적 사고로만 문제를 해결하던 저한테는 충격으로 다가왔습니다. 재귀의 문제를 작게 쪼게는 것에 초점을 마춰서 코드를 설계하는 것이 아닌 규칙을 명확하게 정의하면 재귀 포인트는 알아서 설계가 된다는 뜻 입니다. 이는 하단의 예제를 통해 설명하겠습니다.

 

재귀는 2가지 필수 조건이 있는데, 이는 기저 조건(Base Case)과 재귀 조건(Recursive Case) 입니다.

 

기저 조건(Base Case) 이란 재귀가 끝나는 지점을 의미하는데, 이는 규칙이 종료되는 시점으로 해석할 수 있습니다. 예를 들어 팩토리얼일 경우 N부터 1까지 곱하는 것이기 때문에 현재 곱하려는 수가 1이 되면 규칙이 끝나는 기저 조건이 됩니다. 하노이의 탑을 예를 들면 맨 밑에 있는 도넛이 원하는 위치에 도달 했을 때가 기저조건이 됩니다.

 

재귀 조건(Recursive Case) 은 규칙이 반복되는 구간을 의미합니다. 팩토리얼로 예를 들면 N(현재값)이랑 N-1이 곱해지는 것을 의미하며, 하노이 탑에서는 도넛들이 지정된 규칙을 따라 원하는 포인트로 이동하는 것을 의미합니다. 문제가 작게 쪼개지는 것은 이 재귀 조건의 규칙을 코드로 구현하는 과정에서 구현이 됩니다.

 

보통 코드를 설계하거나 코드가 잘 짜여졌는지 검토할 때, 주어진 조건에 따라 입력값 몇개를 코드에 대입해봅니다. 하노이의 탑에서는 도넛이 1개인 경우, 2개인 경우 4개인 경우 등등. 하지만 이런 절차적인 프로세스로 코드를 검토할때 생각의 길을 읽기가 쉽습니다, 계속 재귀 함수안에서 값이 돌고돌기 때문에. 그렇기 때문에 설계나 검토할 때, 내가 정의한 규칙이 올바른지, 코드는 해당 규칙에 입각하여 설계되었는지 검토하는 것이 바람직하다고 생각합니다.

 

예제: 재귀를 이용한 팩토리얼 계산

​

 

팩토리얼의 규칙은 매우 단순합니다:

• 기저 조건(Base Case): 0! = 1
• 재귀 조건(Recursive Case): n! = n × (n-1)!

위 규칙만 파악하면, 팩토리얼을 계산하는 재귀 함수는 매우 간단하게 작성할 수 있습니다.

코드 구현: 재귀적 사고로 팩토리얼 계산

#include <stdio.h>

// 재귀를 이용한 팩토리얼 함수
int factorial(int n) {
    if (n == 0) return 1; // 기저 조건
    return n * factorial(n - 1); // 재귀 조건
}

int main() {
    int n = 5;
    printf("팩토리얼 %d! = %d\n", n, factorial(n)); // 출력: 120
    return 0;
}

코드 설명

1. 기저 조건(Base Case):
   • n == 0일 때, 팩토리얼은 1로 반환됩니다.
2. 재귀 조건(Recursive Case):
   • n!은 n × (n-1)!로 정의되므로, 함수는 자기 자신을 호출하며 문제를 점차 축소합니다.

---

재귀적 사고의 어려운점

 

위에서 언급햇듯이, 저는 규칙을 강조하고 있습니다. 하지만 재귀적 사고의 가장 큰 장애물도 이 규칙입니다 : 정의된 규칙이 올바른지 여부를 스스로 검토하기가 어렵습니다.

예를들어 절차적 사고로 설계된 코드인 경우 이슈 발생 지점을 처음부터(혹은 중간부터) 플래그를 꽂으면서 한단계 한단계 검토해나가서 찾아낼 수도 있으며, 이슈 발생 지점부터 재설계하거나 디버깅을 할 수 있습니다. 하지만 재귀적 사고로 설계된 코드인 경우 에러를 찾기 위해 하나씩 비교해나가기 시작하면 앞서 말했듯이 반복되는 재귀함수안에서 길을 잃어버리게 됩니다. 결국은 규칙의 정당성을 의심하고 코드가 규칙을 잘 준수하고 있는지 확인하는 것이 재귀적 코드의 디버깅 과정입니다. 전자인 규칙이 틀릴경우 해당 코드 전체가 의미를 잃게 될 확률이 높기 때문에 현타가 자주 오는 것 같습니다. (후자일 경우 그나마 다행이지만)

---

결론 (Conclusion)

절차적 사고와 재귀적 사고는 알고리즘 설계에서 가장 기본적인 사고방식으로, 문제의 성격에 따라 적절히 선택해야 합니다. 절차적 사고는 직관적이고 메모리 효율적인 방식으로 반복적 계산에 적합하며, 재귀적 사고는 문제를 작게 나누어 해결하는 데 강점이 있습니다.절차적 사고와 재귀적 사고는 모든 알고리즘 설계의 기초를 이루며, 분할 정복 사고 (Divide and Conquer Thinking) , 최적화 사고 (Optimization Thinking)로 가기 위한 핵심 사고방식입니다.

 

규칙을 정의하고 이를 코드로 전환하는 연습을 앞으로 진행하고 진행사항에 대해 차후 포스팅하겠습니다.

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.