복습겸. 이것저것 겸해서 재귀에대해서 정리해볼까한다.
재귀함수란?
재귀함수란 함수 내부에서 자기 자신을 호출하는 함수를 말합니다. 이를 통해 반복적인 작업을 수행하거나 문제를 분할하여 해결하는 등 다양한 기능을 구현할 수 있습니다.
재귀함수를짤때 고려해야할것
재귀함수를 짤 때 고려해야 할 것은 종료 조건입니다. 재귀 함수는 자기 자신을 호출하여 반복적인 작업을 수행합니다. 그러나 이를 무한 반복하지 않기 위해서는 종료 조건이 충족될 때까지만 반복해야 합니다. 그럼 종료조건을 설정했다면 그다음엔 뭘해야하냐 문제에서 어떤것을 요구하는지 즉 문제의정의를 알맞게 코딩해주면된다.(재귀함수를통해)
팁!
1.문제를 동일한방식으로 쪼개기(recursive case)
2.더이상 안쪼개지면 그것이 (base case)->이녀석이 탈출조건
3.base case=>요걸 해결하기(이떄 재귀함수가들어감)
문제적용은 음.. 이전에 간단하게 작성한 콜라문제를 가져올까한다.
문제
한 마트에서는 빈 병 a개를 가져다가 주면 콜라 b병을 줍니다. 이 때 빈 병 n개를 마트에 가져다주었을 때 콜라 몇 병을 받을 수 있는지 계산하세요. 빈 병이 a개 미만인 경우에 더 이상 콜라를 받을 수 없습니다. (예시: a가 3, b가 1, n이 20이라고 가정했을 때, 빈 병 3개를 가져다주면, 콜라 1병을 받습니다. 처음에는 빈 병 3개당 콜라 1개를 받을 수 있으므로 빈 병 18개를 가져다주면 콜라 6병을 받게 됩니다. 그리고 콜라 6병을 모두 마셨다고 가정합니다. 그러면 현재까지 남아 있는 콜라는 총 (2+6) = 8병이 되고 콜라 8병에서 이제 6병을 가져다주면 콜라 2병을 받게 됩니다. 이제 2+2 = 4병이 남게 되며 여기에서 3병을 가져다가 1병을 받으면 총 1+1 = 2병이 남게 됩니다. 3병당 1병을 새로 받으므로 더 이상 받을 수 없습니다. 결론적으로 받은 콜라의 병 개수는 6+2+1 = 9개입니다
-->문제가너무길다; 간단하게 요약하면 내가 콜라빈병을 가져간만큼 개수에따라 새콜라를얻는데 얻은콜라를 마시고 그녀석을 다시 빈병화시켜서 다시 가져다줘서 콜라를얻는 무한동력을 하고싶은 콜라중독자의문제다.
콜라문제에서의 base case는뭘까.. 당연히 콜라빈병을 다가져다줘서 콜라를얻을수없을떄를 말한다.
그럼 콜라빈병을 못가져다주는경우는 간단하게 바꾸기위해 가져다줘야할 빈병보다 내빈병이적을때 이 재귀는 끝이나게된다.
그래서 밑 식대로 짜주면 끝~
function solution(a, b, n) {
let 니가먹은콜라가대체뭐야=0
if(n<a){
return 니가먹은콜라가대체뭐야
}
//남은콜라의개수가 줘야되는병보다 적으면 당연히 콜라는 국물도없다.
//근데사실 그냥 return 을 0으로하는게이쁘다.
let 동냥하듯얻은콜라=Math.floor(n/a)*b
//얻은콜라를 구하는방법은 몫을 구하는 Math.floor로 무자비하게 나머지를 잘라버리자
return 동냥하듯얻은콜라+solution(a,b,(n%a)+동냥하듯얻은콜라)
//근데 사실 나머지는 필요하다 왜(?)->그거에 동냥하듯얻은콜라 더해서 또 콜라를먹을수도있거든
//최종코드는 요런식으로 짜주면된다.
}재귀를사용한 풀이의 문제점
근데 재귀를 사용해서 문제를풀다보면 조금 비효율적인점을 눈치챌수있다. 대표적인 피보나치수열을 구하는 식을
재귀를 통해 작성했다고 해보자 그럼 식이 어떻게될까?
fib(n-2)+fib(n-1)을 계속 반복할것인데
만약 fib(10)과 fib(9)를 구해야한다면 10인경우만 구하면되지만 식에넣으면 처음부터 모든결과값을 다 새로구해야한다. 그러면 수가커지면커질수록 최소조건을 수십번에서 수백번왓다갓다 해야한다는 의미다.
그래서 이러한방식을 보완하기위해 메모이제이션이라는 방법을 활용할수있다.
메모이제이션
메모이제이션은 함수의 결과를 저장해두고, 같은 입력에 대해서는 저장된 결과를 반환하는 것입니다. 이를 이용하여 함수의 실행 속도를 높일 수 있습니다.
예를 들어, 재귀적으로 구현된 함수에서 같은 입력에 대해서는 중복된 계산을 수행하게 됩니다. 이때 메모이제이션을 사용하면 중복된 계산을 줄일 수 있습니다.
메모이제이션을 사용하는 방법은 다음과 같습니다:
- 함수의 결과를 저장할 객체를 생성합니다.
- 함수가 호출될 때마다 입력값을 키로 하여 결과값을 저장합니다.
- 함수가 호출될 때마다 입력값이 이미 저장되어 있는지 확인하고, 저장되어 있다면 저장된 결과값을 반환합니다.
function fibonacci(num, memo) {
memo = memo || {};
//memo = memo || {};는 memo 객체가 undefined나 null인 경우 빈 객체를 생성하는 코드입니다.
//즉, memo 객체가 이미 존재한다면 그대로 사용하고, 존재하지 않는다면 빈 객체를 생성하여 사용합니다.
//이 코드는 함수의 인자로 전달된 memo 객체가 없는 경우를 대비한 것입니다.
//이렇게 하면 함수를 호출할 때마다 memo 객체를 생성하지 않아도 되므로 실행 속도를 높일 수 있습니다.
if (memo[num]) return memo[num];
//if (memo[num]) return memo[num];는 memo 객체에 이미 계산된 결과가 있는지 확인하는 코드입니다.
//만약 memo[num]이 존재한다면, 즉 이미 계산된 결과가 있다면 해당 결과를 반환함
if (num <= 1) return 1;
return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);
}
//return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);는
//memo 객체에 결과를 저장하고 반환하는 코드입니다.이 코드는 피보나치 수열의 n번째 항을 계산할 때,
//n-1번째 항과 n-2번째 항을 더한 값을 반환함
요런식으로 계산을 줄일수있다.
재귀끝!
