오늘은 재귀함수를 처음 들어봄과 동시에
코플릿 문제를 풀어보았다.
아니 너무어려운거 아닌가요...??
프로그래머스 입문풀고있는 나에게 너무 가혹하였다,,,
먼저 재귀란??
컴퓨터 과학에서 재귀란 자신을 정의할 때
자기 자신을 재참조하는 방법 (나무위키 백)
그럼 재귀함수(Recursion Function)이란??
재귀의 설명대로 함수에서 자기 자신을 다시 호출해
작업을 수행하는 방식이다.
그렇기에 특정 분기까지 자기 자신을 계속 호출한다.
주로 반복문을 구현할 때 사용한다.
흔히 사용하는 for, while 등과 같은 반복문으로
구현가능한 로직은 모두 재귀함수로도 가능하고,
그 반대도 역시 가능하다.
재귀 함수의 장단점
장점
- 변수를 여럿 만들 필요가 없다.
예를 들어, 현재 상태를 저장해야 할 경우 변수를 만들기보다 상태를
메서드를 재귀적으로 호출하면서 변경된 상태를 전달함으로써 변수의 수를 줄일 수 있음. - while문이나 for문 같은 반복문을 사용하지 않아서 코드가 간결.
단점
- 지속적으로 함수를 호출하게 되면서
지역변수, 매개변수, 반환값을 모두 process stack에 저장해야한다.
선언한 변수의 값만 사용하는 반복문에 비해 메모리를 많이 사용. - 함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생
재귀함수의 단점 해결방법?? - 꼬리재귀
재귀함수의 가장 큰 문제가 자기 자신을 호출한뒤 결과를 기다리면서
생기는 콜스택의 부하로 인한 메모리 낭비였는데,
꼬리재귀라는 개념을 이용하면 재귀 호출이 끝나는 시점에서
아무 일도 하지않고 바로 결과를 반환하도록 하는 방법으로
함수의 상태 유지 및 추가 연산을 하지 않기에 스택오버플로우를 해결가능
그럼 오늘 푼 코플릿 중에 어렵고 정리가 필요한 문제를
정리해보자!!
base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
recursive case : 그렇지 않은 경우
4번 / fibonacci
나의 풀이
base case : num<=1 이면 문제를 더이상 쪼갤 수 없으므로
num이 1이하가 되면 num을 반환하게 한다.
recursive case : 더 작은문제로 계속 쪼갤 수 있을 때
매개변수가 num-1, num-2인 fibonacci 함수를
더해준 값을 반환해준다.
13번 / findMatryoshka
나의 풀이
base case : matryoshka.size===size 이면 문제를 더이상 쪼갤 수 없으므로
true를 반환하게 한다.
recursive case : 더 작은문제로 계속 쪼갤 수 있을 때
14번 / unpackGiftbox
나의 풀이
반복문을 통해 배열, 문자열안에 있는 giftBox을 하나씩 돈다.
base case : 반복문을 통해 요소인 giftBox[i]를 돌면서
매개변수로 들어온 wish와 동일하면 true를 반환
recursive case : 더 작은문제로 계속 쪼갤 수 있을 때
요소인 giftBox[i]가 배열일때
unpackGiftbox함수를 한번 더 호출한다.
그안에 wish와 동일한게 있으면 true를 반환
