한국어
메뉴

재귀(Recursion)란?

함수가 처리 도중에 자기 자신을 호출하는 것. 문제를 같은 형태의 작은 문제로 나누어 풀고, 더 이상 나누지 않는 경우(기저 사례)에서 호출을 끝낸다. 호출마다 스택을 사용하므로 너무 깊으면 넘친다. 마지막에 자신을 호출하기만 하는 꼬리 재귀는 루프로 변환할 수 있다.

일본어 명칭: 再帰

재귀(Recursion)은(는) 자료 구조와 알고리즘, 링커, 로더, 실행 파일, 프로그래밍의 기초(의사 코드 트레이스) 등 8개 분야의 연습 문제 14개에 나와요.

분야: 자료 구조와 알고리즘

도전해 보기: 재귀(Recursion) 관련 문제

RISC-V에서 자기 자신을 호출하는 재귀 함수를 작성할 때 ra를 스택에 저장하는 것을 잊으면 어떻게 되는가?

  1. A안쪽 호출에서 ra가 덮어써져 바깥쪽 함수가 올바른 호출 원본으로 복귀하지 못하게 된다
  2. BCPU가 자동으로 ra를 저장하므로 아무 문제도 일어나지 않는다
  3. C재귀의 깊이와 관계없이 계산 결과가 2배가 된다
정답과 해설 보기

정답: A. 안쪽 호출에서 ra가 덮어써져 바깥쪽 함수가 올바른 호출 원본으로 복귀하지 못하게 된다

재귀 호출의 jal은 ra를 '자신 안의 호출 다음 명령어'로 덮어씁니다. 저장하지 않으면 바깥쪽 함수가 ret할 때 원래 호출 원본이 아니라 자신 안으로 되돌아가 버려 같은 곳을 반복하거나 오동작합니다. 그래서 다른 함수를 호출하는 함수는 프롤로그에서 ra를 스택에 저장하고 에필로그에서 되돌리는 것이 규칙입니다.

재귀가 너무 깊어져 스택 상한을 넘었을 때 Linux 등에서 일반적으로 일어나는 일로 올바른 것은 무엇입니까?

  1. A스택 끝에 있는, 접근을 금지한 가드 페이지에 닿아 프로그램이 비정상 종료된다
  2. BOS가 자동으로 스택을 디스크로 옮겨 얼마든지 깊게 재귀할 수 있다
  3. C오래된 스택 프레임이 자동으로 지워지고 계산은 올바르게 이어진다
정답과 해설 보기

정답: A. 스택 끝에 있는, 접근을 금지한 가드 페이지에 닿아 프로그램이 비정상 종료된다

스택에는 상한이 있고 그 끝에는 접근을 금지한 가드 페이지가 놓여 있습니다. 재귀가 너무 깊어 스택이 여기에 도달하면 페이지 폴트가 발생하여 OS가 프로그램을 멈춥니다(세그멘테이션 오류). 다른 데이터를 망가뜨리기 전에 멈출 수 있는 것이 가드 페이지의 이점입니다. 큰 배열을 지역 변수로 해도 같은 일이 일어나므로 큰 데이터는 힙에 두는 것이 안전합니다.

해설 속 재귀(Recursion)

재귀(Recursion)이(가) 나오는 문제 (14)

  1. RISC-V에서 자기 자신을 호출하는 재귀 함수를 작성할 때 ra를 스택에 저장하는 것을 잊으면 어떻게 되는가?
  2. 위의 함수의 마지막 재귀 호출에 꼬리 호출 최적화를 적용하면 어떤 효과가 있는가?
  3. 재귀가 너무 깊어져 스택 상한을 넘었을 때 Linux 등에서 일반적으로 일어나는 일로 올바른 것은 무엇입니까?
  4. 간선에 방향이 없는 그래프에서 각 정점의 이웃 정점이 다음과 같다. A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. 정점 A부터 재귀적인 깊이 우선 탐색을 수행한다. 이웃 정점은 여기에 쓴 순서로 조사하고, 아직 방문하지 않은 정점이 발견되면 바로 그 정점으로 나아간다. 정점을 방문하는 순서는?
  5. 피보나치 수를 구하는 함수 fib(n)을 'n이 1 이하이면 n을 반환하고, 그렇지 않으면 fib(n−1) + fib(n−2)를 반환한다'로 재귀적으로 정의했다. fib(5)를 호출했을 때 fib가 호출되는 횟수는 첫 호출을 포함하여 몇 회인가?
  6. 프로그램에서 서브루틴(함수)을 호출할 때 복귀 주소 등을 일시적으로 저장하기 위해 일반적으로 사용되는 영역은?
  7. C 언어 함수 안에서 선언한, static이 붙지 않은 지역 변수(자동 변수)는 실행 중 어디에 놓입니까?
  8. 프로세스의 힙과 스택을 사이에 넓은 빈 공간을 두고 반대 방향으로 늘어나는 배치로 하는 이점으로 올바른 것은 무엇입니까?
  9. MMU가 없는 작은 마이크로컨트롤러에서 스택 과다 사용에 대해 주의해야 할 점으로 올바른 것은 무엇입니까?
  10. 간선에 가중치가 없는 그래프에서, 출발점에서 각 정점까지의 최소 간선 수를 구하고 싶다. 적합한 탐색 방법과 그때 사용하는 자료 구조의 조합은?
  11. 함수 f(x, y)를 'y가 0이면 x를 반환하고, 그렇지 않으면 f(y, x mod y)를 반환한다'로 정의한다. f(84, 36)을 호출했을 때의 반환값과, f가 호출되는 횟수(첫 호출 포함)의 조합은?
  12. ÷는 나눗셈이며, 정수형 변수(인수 포함)에 대입할 때는 소수점 이하를 버린다. 다음 함수 pow를 pow(2, 10)으로 호출했을 때, pow가 호출되는 횟수(최초 호출 포함)는?
  13. 다음 함수 fib를 fib(10)으로 호출했을 때의 반환값은?
  14. int는 32비트(최댓값 2147483647)로 한다. 위의 함수 fact(n)이 n의 계승을 오버플로 없이 올바르게 반환하는 최대의 n은?

관련 용어

스택(Stack) 변수(Variable) 인수(Argument) 배열(Array) 반환값(Return Value) 스택 프레임(Stack Frame) 깊이 우선 탐색(Depth-First Search) 너비 우선 탐색(Breadth-First Search) 스택 포인터(stack pointer) 페이지 폴트(page fault)

용어집으로 돌아가기