자기 자신을 부르는 함수를 재귀함수라고 한다.
많은 연산을 필요로 하는 프로세스를 짤 때
시간복잡도
에서 중요하게 보는 n의 단위를 작게 만들어,
프로세스의 실행 시간과 횟수를 효율적으로 만들 수 있다.
이는 곧 stackOverflow
에 도달하지 않는 것을 목표로 한다고 볼수 있다.
함수는 호출시 콜 스택
이라는 곳에 stack
으로 쌓이기 시작한다.
처음 호출시 쌓이기 시작해, 함수가 끝날 때 까지 쌓여,
실행되기 시작하는 함수부터 처음 쌓인 함수까지 실행된다.
실행이 될때마다 함수는 콜 스택에서 빠져나가는 것이다.
알고리즘 작성시, 재귀적으로 표현하여 호출 하는것이 자연스러울때
재귀함수를 쓰게 된다.
그러나, 재귀함수는 콜 스택
의 메모리를 많이 잡아먹으므로,
stackOverflow
가 발생하지 않는 한계선까지 사용을 해야한다.
function yoon(n) {
if (n <= 1) {
console.log('마지막 스택 n은 ' +n)
return 1 // 조건 만족시 반환할 return값
} else {
let answer = yoon(n - 1)
console.log('n은 ' + n)
console.log(n + answer)
return n + answer // yoon(n) 함수 안에서 yoon(n-1) 함수를 호출
}
}
console.log(yoon(5));
함수 yoon에 파라미터(5)를 넣을시,
최초 n = 5 부터 if문을 시작하게 된다.
if (n <= 1) // false
false 실행 문구에서
return n + yoon(n-1)
파라미터(5)에 함수 yoon(n-1)
의 반환값을 더해줘서
return
하고 함수yoon(n)
을 마쳐야 한다....
return 5 + yoon(5-1)
그러나
return n + yoon(n-1)
함수 yoon(n-1)
의 반환값이 연산되지 않았으므로
컴퓨터는 함수 yoon(n)
을 연산하기 위해 본인의 함수 yoon(n-1)
을 연산하게 된다.
동시에
return이 예약(?) 되었으므로 콜 스택
의 첫번째 블럭을채우게 된다.
return 5 + yoon(5-1)
이제 function yoon(4) {
를 연산하기 시작한다.
n이 4이므로 false가 나오고
return 4 + yoon(4-1)
마찬가지로 콜 스택
의 두번째 블럭을 채우고,
yoon(4-1)
을 반환하기 위한 function yoon(3)
을 연산하기 시작.
그리고 반복
return 3 + yoon(3-1)
return 2 + yoon(2-1)
콜 스택
은 꾸준히 쌓여
밑에서 부터
return 2 + yoon(2-1)
return 3 + yoon(3-1)
return 4 + yoon(4-1)
return 5 + yoon(5-1)
4번째 블럭까지 채우게 된다.
function yoon(1)
이제 if
조건문 n <= 1
을 만족(true
)하였고,
return 1
1
을 반환한다.
function yoon(2-1)
의 return
값이 1
이 반환되었다.
이제 컴퓨터는
return 2 + yoon(2-1)
을 연산할 수 있다.
첫번째 블럭 return 2 + 1
을 연산하여 3
을 반환했다.
이는 곧
두번째 블럭 yoon(3-1)
의 반환값 이므로
return 3 + yoon(3-1)
도 연산이 가능해진다.
이제 최초로 추가된 블럭까지 pop
한다.
return 3 + yoon(3-1) // 3+3 = 6
return 4 + yoon(4-1) // 4+6 = 10
return 5 + yoon(5-1) // 10+5 = 15
첫번째 블럭 함수의 리턴값은
function yoon(5) // 파라미터로 받은 값 n=5
15
였으니, 반환되며 pop
된다.
console.log(yoon(5)) // 15
15
가 출력값으로 콘솔에 찍히게 된다.
다이나믹 프로그래밍
으로 대표되는 피보나치 수열
프로세스는
시간복잡도 n*n으로 작성시 콜 스택
을 굉장히 많이 차지하게되는 문제가 생긴다.
이는 콜 스택
이 무거워 짐을 뜻하고, 연산이 느려짐을 말한다.
다음 시간에는 피보나치 수열
프로세스를 작성하면서
콜 스택
공간을 절약하는 방법을 알아보자.
return fibo2(n) {
if(n == i || n==2) {
return 1
}
return fibo2(n-1) + fibo2(n-2)
}
let number = [1,1]
return fibo3(n) {
if(number[n-1] > 0) {
return 1
} else if (number[n-1] > 0) {
return number[n-1]
} else {
return fubo3(n-1) + fibo3(n-2)
}
}