인프런 커뮤니티 질문&답변
작성한 질문수
더하거나 빼거나 문제 질문
해결된 질문
작성
·
71
0
1. 현재 학습 진도
몇 챕터/몇 강을 수강 중이신가요?
2-10 챕터
어떤 알고리즘을 학습하고 계신가요?
더하거나 빼거나 문제
여기까지 이해하신 내용은 무엇인가요?
2. 어려움을 겪는 부분
어느 부분에서 막히셨나요?
재귀함수
코드의 어떤 로직이 이해가 안 되시나요?
get_all_ways_by_doing_plus_or_minus(array, current_index + 1, current_sum + array[current_index])
get_all_ways_by_doing_plus_or_minus(array, current_index + 1, current_sum - array[current_index]
제가 이해 안가는것은 처음에 cur_index = 0 , cur_sum = 0 부터 시작하잖아요
get_all_ways_by_doing_plus_or_minus(array,1,2)
get_all_ways_by_doing_plus_or_minus(array,1,-2)
그러고 다음 cur_index = 1 , cur_sum = 2 이렇게 흘러가는데,
왜 get_all_ways_by_doing_plus_or_minus(array,1,-2) -2 가 안가고 +2 가 가는지 궁금합니다.
get_all_ways_by_doing_plus_or_minus(array, current_index + 1, current_sum + array[current_index]) 계산이 전부 끝난 뒤에
get_all_ways_by_doing_plus_or_minus(array, current_index + 1, current_sum - array[current_index] 가 이어서 오는건가요 ?
어떤 개념이 헷갈리시나요?
3. 시도해보신 내용
문제 해결을 위해 어떤 시도를 해보셨나요?
에러가 발생했다면 어떤 에러인가요?
현재 작성하신 코드를 공유해주세요
이렇게 구체적으로 알려주시면, 더 정확하고 도움이 되는 답변을 드릴 수 있습니다! 😊
답변 1
0
안녕하세요 오승택님! 좋은 질문 감사합니다
재귀 함수에 대한 질문에 답변드리겠습니다!
이 코드에서 가장 이해하기 어려운 부분은 재귀 호출의 실행 순서입니다. 학생이 혼란스러워하는 부분을 명확히 설명해 드리겠습니다.
재귀 함수가 실행되는 방식은 "깊이 우선 탐색(DFS)"이라고 생각하시면 됩니다. 첫 번째 재귀 호출이 완전히 끝날 때까지 두 번째 재귀 호출은 대기하게 됩니다.
원리를 다음과 같이 설명해 드리겠습니다!
처음에
get_all_ways_by_doing_plus_or_minus(array, 0, 0)으로 시작합니다.이 함수는 두 개의 재귀 호출을 합니다:
get_all_ways_by_doing_plus_or_minus(array, 1, 0+1)→(array, 1, 1)(더하는 경우)get_all_ways_by_doing_plus_or_minus(array, 1, 0-1)→(array, 1, -1)(빼는 경우)
중요한 점은 첫 번째 호출
(array, 1, 1)이 완전히 끝날 때까지 두 번째 호출(array, 1, -1)은 실행되지 않습니다.(array, 1, 1)호출은 다시 두 개의 호출을 생성합니다:(array, 2, 1+1)→(array, 2, 2)(array, 2, 1-1)→(array, 2, 0)
이런 식으로 첫 번째 경로가 끝(배열의 마지막 요소)까지 도달한 후에야 다음 경로가 탐색됩니다.
이것을 트리로 시각화하면 이렇게 됩니다!!
(0,0)
/ \
(1,1) (1,-1)
/ \ / \
(2,2) (2,0) (2,0) (2,-2)
... 이런 식으로 계속됨코드 실행 순서는 깊이 우선이기 때문에,
(0,0) → (1,1) → (2,2) → ... → 끝까지 간 후
(0,0) → (1,1) → (2,0) → ... → 끝까지 간 후
(0,0) → (1,-1) → (2,0) → ... → 끝까지 간 후
(0,0) → (1,-1) → (2,-2) → ... → 끝까지
따라서 get_all_ways_by_doing_plus_or_minus(array, 1, -2)는 건너뛰는 것이 아니라, get_all_ways_by_doing_plus_or_minus(array, 1, 1)의 모든 하위 호출이 완료된 후에야 실행됩니다.
좋은 질문 감사드립니다! 한 번 디버그 모드 등을 이용해서 순서를 살펴보시는것도 좋을 것 같습니다 혹시 더 궁금하신 점ㅇ 있으시면 편하게 더 질문해주세요! ㅎ.ㅎ