재귀함수란?
함수 내에서 자기 자신을 계속해서 호출하는 함수를 의미합니다.
스택 프레임
함수가 호출될 때 그 함수만의 스택 영역을 구분하기 위해 생성되는 공간을 의미합니다. 이 스택에는 함수와 관련되는 매개변수,지역변수,복귀주소가 저장되며 함수가 호출될 시 생성되고 소멸될 시 삭제됩니다.
예시 1
자연수 N이 입력되면 1~N까지 출력하는 프로그램을 작성하시오
(재귀 함수를 이용)
function solution(n) {
function DFS(L) {
if (L === 0) return;
else {
DFS(L - 1)
console.log(L);
}
}
DFS(n);
}
solution(3);우선 함수 내에서 자기 자신을 계속해서 호출할 때 종료 조건을 제시해주지 않는다면 무한루프에 걸릴 가능성이 높다. 때문에 재귀함수를 이용할때는 반드시 종료조건을 걸어줘야 한다.
그림으로 위 코드를 설명해 보자면 (다른 블로그에서 퍼옴)
처음에 내가 스택 프레임에 관해서 설명했다. 위 코드를 보면
처음에 DFS(3)이 호출되고 Stack에 쌓인다. 이 때 그 다음줄인 console.log()를 실행하는것이 아니라 Stack에 쌓인 상태로 대기상태가 된다. 그 다음 DFS(2)를 호출하고 마찬가지로 스택에 쌓임 , ... DFS(1) ... DFS(0)까지 반복하고 이때 DFS(0)을 호출하면 첫번째 조건문에 의해서 함수를 종료하게 된다.
스택 프레임의 관점에서 봤을때 pop()되고 아직 대기중인 DFS(1)의 복귀주소로 가서 남은 console.log()를 실행한다. 이렇게 스택에 대기중인 스택 프래임이 없을때까지 반복하게 되면 1,2,3이 호출된다.
예시 2
10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 만드세요, 단 재귀함수 이용
2진수를 구하는 방식은 2로 나누었을때 나머지를 구하는 방식과 같음
function solution(n) {
let answer = '';
function DFS(n) {
if (n === 0) return;
else {
DFS(parseInt(n / 2));
answer += String(n % 2);
}
}
DFS(n);
return answer;
}
사실상 예시 1과 다름없는 문제다.
우선 10진수를 2진수로 변환하는 방법은 js의 toString(2) 메서드를 사용하는 방식도 있지만 재귀 함수를 사용하여 구현해야하기 때문에 2로 나눈 나머지를 더해주는 방식으로 구현했다. (2로 나눈 몫이 0이 될때까지)
스택프레임의 관점에서 다시 한번 분석해보자
예를 들어 n이 11로 주어진다고 가정해보면
처음에
DFS(11)이 Stack에 쌓인다. 그 다음 대기 상태가 되고
DFS(5)가 Stack에 쌓인다. ...
DFS(2) ... ...
DFS(1) ... ...
DFS(0) -> return , 즉 함수의 종료 이때 stack에서 pop()되고
각각의 스택프래임들은 자신의 복귀주소를 가지고 있기 때문에
DFS(1)부터 DFS(11)까지 answer += String(n % 2) 를 실행하고 Stack에서 pop() 된다.
예시 3(무지성으로 재귀를 쓰진 말자)
재귀 함수로 더 구현해보고 싶은 욕심이 생겨서 프로그래머스 lv2.피보나치 순열 구하기 문제에 도전해보았다.
처음에 무지성으로 피보나치로 구현해야지하고 접근했는데 실행초과 및 런타임에러에 걸려버렸다...
런타임 초과된 코드
function solution(n) {
var answer = 0;
if (n <= 1) {
return n;
} else if (n >= 2) {
return solution(n - 1) + solution(n - 2);
}
}
예를 들어 n에 11이 주어지면
return solution(10) + solution(8) 인데 여기서 또 solution(10)을 구하려면 solution(9)+solution(8)
solution(8)을 구하려면 solution(7)+solution(6)
....
마치 트리 형태처럼 계속해서 답을 유추해나갈 것이고 트리의 끝에 닿았을때 (n이 1 혹은 2 일때) 반환값을 알아내어 역으로 계속 유추해나갈 것이다. 이는 얼핏 보아도 시간복잡도가 엄청날 것이고 성능상 좋지 않아보인다.
그래서 우선은 단순 반복문으로 코드를 해결해보았다.
function solution(n) {
var answer = [];
for (let i = 0; i <= n; i++) {
if (i === 0) answer.push(0);
if (i === 1) answer.push(1);
if (i >= 2) {
let sum = answer[i - 1] + answer[i - 2];
answer.push(sum % 1234567);
}
}
let result = answer[n];
return result;
}처음 구현한 코드와 비슷하긴 하지만 answer라는 배열에 피보나치 수를 n 전까지 계속해서 계산하기 때문에 o(n)만큼의 시간 복잡도를 가진다.
정리
재귀함수 -> 자기 자신을 계속해서 호출하는 함수
스택 프래임 -> 함수가 호출될 때 그 함수의 스택 영역을 구분하기위해 생기는 공간(지역변수,매개변수,복귀주소)
주의할 점 -> 함수가 호출되면 하던 일을 멈추고 대기 상태가 되어 다음 호출한 함수를 실행하는데 이때 stack에 쌓이고 특정한 조건에 의해서 호출을 종료하면 그때서야 stack에 쌓인 순서와는 반대로 호출한 자신의 복귀주소로 돌아가 남은 코드를 실행하고 스택에서 pop()된다.
얼핏 보면 호출하고 바로 다음 코드를 실행할 것 같은데 스택 프래임의 원리를 알면 이해하기 쉬운 코드다. 무지성으로 호출후 다음 코드로 읽어 내려가지 말자.
- 재귀함수는 시간복잡도상 복잡해질 수 있기 때문에 다른 방식으로도 생각해보자
