LV15 꼬리재귀 마스터 - 20문제 연습집 (Tail Recursion Practice)

// ❌ 일반 재귀 (스택 쌓임) int factorial(int n) { if (n <= 1) return 1; return n * factorial(n-1); // 곱셈 후 재귀 호출 } // ✅ 꼬리재귀 (스택 재사용 가능) int factorial_tail(int n, int acc = 1) { if (n <= 1) return acc; return factorial_tail(n-1, acc * n); // 재귀 호출이 마지막 }

path[level + 1] = value[i]; visited[i] = 1; run(i, level + 1); // 재귀 호출 path[level + 1] = 0; // ← 재귀 호출 후에 실행 → 꼬리재귀 불가능

#include <iostream> char value[6] = "IEQWA"; char path[6] = ""; int visited[5] = {}; int map[5][5] = { 0,1,0,0,0, 0,0,1,1,0, 0,0,0,0,0, 1,0,0,0,1, 0,0,0,0,0, }; void run(int now, int level) { std::cout << value[now]; for (size_t i = 0; i < 5; i++) { if (map[now][i] == 1 && visited[i] == 0) { path[level + 1] = value[i]; visited[i] = 1; run(i, level + 1); path[level + 1] = 0; } } } int main() { path[0] = 'T'; visited[0] = 1; run(0, 0); return 0; }

void run_tail(int now, int level, int visited[], char path[]) { std::cout << value[now]; for (size_t i = 0; i < 5; i++) { if (map[now][i] == 1 && visited[i] == 0) { int newVisited[5]; memcpy(newVisited, visited, sizeof(int)*5); char newPath[6]; memcpy(newPath, path, sizeof(char)*6); newPath[level + 1] = value[i]; newVisited[i] = 1; // 재귀가 마지막 실행 run_tail(i, level + 1, newVisited, newPath); } } }

#include <stack> struct State { int now, level; int visited[5]; char path[6]; }; void run_iterative() { std::stack<State> st; State start{}; start.now = 0; start.level = 0; start.visited[0] = 1; start.path[0] = 'T'; st.push(start); while (!st.empty()) { State cur = st.top(); st.pop(); std::cout << value[cur.now]; for (size_t i = 0; i < 5; i++) { if (map[cur.now][i] == 1 && cur.visited[i] == 0) { State next = cur; next.level++; next.path[next.level] = value[i]; next.visited[i] = 1; st.push(next); } } } }

// 문제: n! 을 꼬리재귀로 구현하세요 int factorial_tail(int n, int acc = 1) { // TODO: 여기에 구현 } // 테스트: factorial_tail(5) = 120

// 문제: base^exp 를 꼬리재귀로 구현하세요 int power_tail(int base, int exp, int acc = 1) { // TODO: 여기에 구현 } // 테스트: power_tail(2, 10) = 1024

// 문제: n번째 피보나치 수를 꼬리재귀로 구현하세요 int fibonacci_tail(int n, int a = 0, int b = 1) { // TODO: 여기에 구현 } // 테스트: fibonacci_tail(10) = 55

// 문제: 1+2+3+...+n 을 꼬리재귀로 구현하세요 int sum_tail(int n, int acc = 0) { // TODO: 여기에 구현 } // 테스트: sum_tail(100) = 5050

// 문제: 유클리드 호제법을 꼬리재귀로 구현하세요 int gcd_tail(int a, int b) { // TODO: 여기에 구현 } // 테스트: gcd_tail(48, 18) = 6

// 문제: 배열의 모든 원소 합을 꼬리재귀로 구현하세요 int array_sum_tail(vector<int>& arr, int index = 0, int acc = 0) { // TODO: 여기에 구현 } // 테스트: {1,2,3,4,5} → 15

// 문제: 배열에서 최댓값을 꼬리재귀로 찾으세요 int array_max_tail(vector<int>& arr, int index = 0, int max_val = INT_MIN) { // TODO: 여기에 구현 } // 테스트: {3,1,4,1,5,9,2} → 9

// 문제: 문자열을 꼬리재귀로 뒤집으세요 string reverse_tail(string str, int start = 0, int end = -1) { if (end == -1) end = str.length() - 1; // 초기화 // TODO: 여기에 구현 } // 테스트: "hello" → "olleh"

// 문제: 문자열이 팰린드롬인지 꼬리재귀로 검사하세요 bool is_palindrome_tail(string str, int start = 0, int end = -1) { if (end == -1) end = str.length() - 1; // TODO: 여기에 구현 } // 테스트: "racecar" → true, "hello" → false

// 문제: 10진수를 이진수 문자열로 꼬리재귀 변환하세요 string to_binary_tail(int n, string result = "") { // TODO: 여기에 구현 } // 테스트: 10 → "1010"

// 문제: 배열에서 target 값의 개수를 꼬리재귀로 세어보세요 int count_target_tail(vector<int>& arr, int target, int index = 0, int count = 0) { // TODO: 여기에 구현 } // 테스트: {1,2,3,2,2,4}, target=2 → 3

// 문제: 연결리스트를 꼬리재귀로 뒤집으세요 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverse_list_tail(ListNode* head, ListNode* prev = nullptr) { // TODO: 여기에 구현 } // 테스트: 1→2→3 을 3→2→1 로

// 문제: 정렬된 배열에서 target을 꼬리재귀로 찾으세요 int binary_search_tail(vector<int>& arr, int target, int left = 0, int right = -1) { if (right == -1) right = arr.size() - 1; // TODO: 여기에 구현 } // 테스트: {1,3,5,7,9}, target=5 → index 2

// 문제: 퀵소트의 분할을 꼬리재귀로 구현하세요 int partition_tail(vector<int>& arr, int low, int high, int i = -1, int j = -1) { if (i == -1) i = low - 1; // 초기화 if (j == -1) j = low; // 초기화 // TODO: 여기에 구현 (pivot = arr[high]) } // 테스트: 분할 후 피벗의 최종 위치 반환

// 문제: 이진트리를 꼬리재귀로 중위순회하세요 (스택 시뮬레이션) struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void inorder_tail(TreeNode* root, vector<int>& result, stack<TreeNode*>& stk) { // TODO: 여기에 구현 }

// 문제: 이진트리의 높이를 꼬리재귀로 구하세요 int tree_height_tail(TreeNode* root) { // TODO: 여기에 구현 // 힌트: 서브트리들의 최대 높이를 비교 }

// 문제: 미로에서 출구까지의 경로를 꼬리재귀로 찾으세요 bool maze_dfs_tail(vector<vector<int>>& maze, int x, int y, int target_x, int target_y, vector<vector<bool>>& visited) { // TODO: 여기에 구현 // 0=길, 1=벽, 시작점에서 목표점까지 경로 존재 여부 }

// 문제: n개 중 r개를 선택하는 모든 조합을 꼬리재귀로 생성하세요 void combinations_tail(vector<int>& nums, int r, vector<int>& current, vector<vector<int>>& result, int start = 0) { // TODO: 여기에 구현 } // 테스트: {1,2,3,4}에서 2개 선택 → {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

// 문제: 하노이의 탑을 꼬리재귀로 해결하세요 void hanoi_tail(int n, char from, char to, char aux, vector<string>& moves) { // TODO: 여기에 구현 } // 테스트: 3개 원판을 A에서 C로 이동 (B를 보조로 사용)

// 문제: 2^p - 1 형태의 메르센 소수를 꼬리재귀로 검사하세요 bool is_mersenne_prime_tail(int p, long long divisor = 3, long long mersenne = -1) { if (mersenne == -1) mersenne = (1LL << p) - 1; // 2^p - 1 // TODO: 여기에 구현 } // 테스트: p=5일 때 31은 소수인가? (2^5-1 = 31)