재귀 함수 단점에 대한 궁금증입니다.
재귀 함수 단점이 결과 값을 구하기 위해
앞선 값들을 새롭게 계산해야 해서 중복 계산해야 하고,
그로 인해 중복된 계산이 많아질 수록 메모리를 매번 많이 잡아먹게 되는 것이 문제라고 설명해주셨는데요.
피보나치 수열을 예로 들었을 때,
최초 한 번 임의의 범위까지 피보나치 수열의 값들을 계산해서 배열에 저장해 놓고, 그 뒤에 원하는 값을 index로 빼서 쓰는 씩으로 메모리 관리와 연산 수를 줄이는 방식으로 하게 될까요?
이런 경우는 어떤 씩으로 프로그램을 개선해 나가는지 궁금합니다 🙏
답변 1
1
안녕하세요? 질문&답변 도우미 durams입니다.
말씀해주신 내용이 맞습니다. 이번 강의 영상에서도 언급되었듯이, 별도의 배열을 사용하여 계산했던 값들을 담아두고 나중에 중복 계산하는 대신 이를 뽑아쓰는 방식을 사용할 수 있습니다. 이러한 접근 방식을 Dynamic Programming이라고 하는데요(사실 정확히는 dynamic programming 문제를 푸는 방법 중 하나입니다), 언어 문법보다는 알고리듬 과목에서 더 자세하게 배우시게 될 내용입니다.
다만 이것이 재귀와 양립 불가능한 개념은 아니에요. 재귀를 하면서 중복 계산을 방지할 수도 있고, 반복으로 알고리듬을 짜고 중복 계산을 방지할 수도 있어요. 전자는 보통 memoization 또는 top-down approach, 후자는 tabulation 또는 bottom-up approach라고 합니다. 알고리듬에 관한 내용은 강의 내용을 벗어나기에 키워드 정도만 제시해드릴 수 있다는 점 양해 부탁드립니다.
또한 재귀가 언제나 나쁜 것은 아닌게, 문제에 따라 재귀로 접근하는 것이 훨씬 이해하기 쉽고 작성이 우아하게 되는 경우도 있어요. 물론 이번 강의 영상에서 언급된 것처럼 재귀 자체에는 제한이 존재하기 때문에 사용 시 염두에 둬야겠죠.
Export template 안됨
1
65
2
완전히 똑같이 따라해도 exe파일이 안만들어져서 실행이 안됩니다.
1
91
3
main 함수에서 왜 int만 선언이 되는걸까요
1
81
2
8비트 2진수 변환시 왜 1을 더해야하나요?
1
75
2
혹시 강의를 빠르게 수강하려면 어디서부터 듣는게 좋을까요?
1
78
1
프로토타입과 함수간의 인자 불일치
1
87
2
12.12 헤더 관련 질문
1
74
2
Visual Studio Community 2026 사용 문의
1
171
2
Q. 15:30, 부호가 있는 8비트 정수 질문
1
72
2
getchar(), putchar()
1
111
3
강의자리ㅛ
1
93
2
비주얼스튜디오코드로 공부해도 상관없나요?
1
127
2
소스파일안에 여러 파일
1
87
2
F5와 F7의 차이
1
90
2
c = TWO * (a+b); 에서 a와 b는?
1
67
2
; 세미콜론을 붙이는 기준에 문의
1
78
1
Step over 기능 문의
1
65
2
2.6 강의 따옴표 출력 규칙 문의
1
87
2
int main 함수 관련 오류 문의
1
76
2
13.4 words[0]
0
73
2
11.7 함수를 구현해 봤습니다.
1
67
2
11.6 직접 strcmp와 strncmp를 구현해 보았습니다.
1
71
2
11.6 my_strcat과 my_strncat을 구현해봤습니다.
1
61
2
11.6 fit_str함수를 구현해 봤습니다.
1
59
2