[면접대비] 재귀함수

재귀함수

함수가 자기 자신을 호출할 때를 뜻한다.

 

재귀함수의 반복되지 않는 조건, 기저조건

함수가 반복되지 않는 경우에 대한 조건을 기저 조건이라 부른다.

기저조건이 없다면 단기 메모리에 더이상 데이터를 저장할 공간이 없을 때까지 호출 스택이 늘어간다.

이 경우 스택 오버플로(stack overflow)오류가 발생하고, 컴퓨터는 재귀를 강제로 중단한다.

 

아래의 카운트다운 함수에서는 0이 기저 조건에 해당한다.

 

재귀함수의 실행 순서

재귀함수는 실행된 함수가 다 끝나기 전 같은 함수가 불리게 된다.

3번 반복되는 재귀함수의 경우 다음과 같이 stack으로 함수를 호출하고 처리한다.

3번 함수와 2번 함수가 다 끝나지 않았으므로 스텍에 남아 있는다.

1번 함수가 return을 반환하여 완료되면 스텍에서 팝하여 제거된다.

차례로 1번 함수의 결과로 2번 함수가 완료되고 팝하여 제거된다.

 

재귀함수를 적용하는 경우

알고리즘이 임의의 단계만큼 깊이 들어가야 하는 경우에는 재귀함수가 좋은 방법이 될 수 있다.

재귀함수를 사용할 때는 불필요한 호출을 줄이는 것이 성능에 영향을 크게 미친다.

이때는 재귀함수를 사용한 값을 변수에 저장하고, 이 값이 사용되는 경우 변수를 적용하는 것이 좋다.

 

아래의 경우 재귀함수인 max가 if에서 조건을 확인하기 위해 한번, 해당하지 않으면 return문에서 한번 더 실행된다.

이 경우 효율은 O(2^n)이 된다.

 

아래의 경우 재귀함수 결과를 lastMax에 저장하여 사용하였다.

함수는 lastMax를 정의할 때 한번 호출되었다.

이 경우 효율은 O(n)이 된다.

 

재귀함수에 동적 프로그래밍 적용

재귀함수를 최적화 하는데 사용되는 방법이다.

이름은 동적 프로그래밍이지만 동적인 요소는 포함하고 있지 않다.

 

1. 메모이제이션(memoization)

먼저 계산한 함수 결과를 해시 태이블로 기억해 재귀 호출을 감소시킨다.

해시 테이블은 함수의 두번째 인자로 전달한다.

해시 테이블에 저장된 값이 없다면 새로운 값을 저장한다.

 

2. 상향식

같은 문제를 재귀 대신 루프 등의 다른 방식으로 해결한다는 뜻이다.

재귀함수를 사용한 방법이라고는 할 수 없고, 반복해서 함수를 사용할 수 있도록 for로 값을 변경하여 적용한다.