재귀 함수
학습하면서 어려웠던 문제를 적어본다.😤
2시간동안 머리싸매고 이걸 어떻게 재귀로 풀수있을까 고민을 했는데
유능하신 페어분께서 멋지게 풀이에 성공하셨다.👏
문제
배열을 입력받아서 순서가 뒤집힌 배열을 반환하는 재귀함수를 만드시오.
함수의 틀
public int[] reverseArr(int[] inputArr) {
// 너의 꿈을 펼쳐봐
}입출력 예시
input : {3, 2, 1}
output : {1, 2, 3}
생각
int[]을 입력받아서 int[]을 리턴하는 재귀 함수로 입력받은 배열을 뒤집으라니
재귀 함수의 탈출 조건을 만드는게 너무 어려웠다.
배열이 뒤집혔다라고 확인할 수 있는 방법이 없어서 재귀 함수를 종료시킬 조건을 어떻게 만들어야하는지 고민을 많이했다.
public int addSum(int[] arr) {
if(arr.length == 0) {
return 0;
}
return arr[0] + addSum(Arrays.copyOfRange(arr, 1, arr.length));
}위와 같이 배열의 크기를 하나씩 줄여가며 배열의 마지막 값을 하나씩 더해주면 되지 않을까 생각했었는데
// 에러! 실행할수도 없는 엉망진창 코드!!
public int[] reverseArr(int[] arr) {
if(arr.length == 0) {
return arr;
}
int[] result = new int[arr.length];
return result = arr[arr.length - 1] + reverseArr(Arrays.copyOfRange(arr, 0, arr.length - 1));
}위의 코드는 배열끼리의 덧셈 연산은 할 수 없기때문에 사용할 수 없었다. 😅
그리고 int[]을 반환값으로 가지며 배열을 합치는 함수는 찾을수 없었다. 😢
Stream을 이용해야 하는건가 이것저것 검색을 해봤지만 적절한 결과는 찾지 못했었다. 😰
꼭 return 에서 재귀 함수를 호출할 필요는 없다라는 생각까지는 했었는데 💡
int[]를 입력받아서 int[]를 리턴하는 재귀 함수를 이용해서
종료 조건을 만들고
배열을 합치는 방법은 생각해내지 못했다. 😭
코딩 천재이신 페어분께서 생각해내신 방법을 봐보자.👍
해법
- 입력받은 배열의 크기가 0이라면 입력받은 배열을 반환한다.
- 배열의 마지막 값을 갖는 배열을 만든다.
- 배열의 마지막 값을 제외한 나머지 값들을 갖는 배열을 만든다.
- 나머지 값들을 갖는 배열을 만들때 reverseArr 함수를 재귀호출하여 만든다.(reverseArr의 반환값이 int[] 이기때문에 바로 배열을 만들수있다.)
- 새로운 배열을 만든다.
- 새로 만든 배열에 마지막 값을 갖는 배열을 앞에 넣어준다.
- 배열에 나머지 값들을 갖는 배열을 붙인다.
- 값들을 넣어준 배열을 반환한다.
재귀 함수를 순서로 적으려니 쓰기도 어렵고 읽기도 어려운것 같다.🤔
코드를 통해 이해하는 편이 훨씬 효율적일 것 같다.
코드
public int[] reverseArr(int[] arr) {
// 1. 입력받은 배열의 크기가 0이라면 입력받은 배열을 반환한다.
if(arr.length == 0) {
return arr;
}
// 2. 배열의 마지막 값을 갖는 배열을 만든다.
int[] head = Arrays.copyOfRange(arr, arr.length - 1, arr.length);
// 3. 나머지 값을 갖는 배열을 만든다.
// 4. 나머지 값을 갖는 배열을 reverseArr 함수에 넣어서 재귀호출 한다.
int[] tail = reverseArr(Arrays.copyOfRange(arr, 0, arr.length - 1));
// 5. 새로운 배열을 만든다.
int[] arrSum = new int[head.length + tail.length];
// 6. 새로 만든 배열에 마지막 값을 갖는 배열을 앞에 넣어준다.
System.arraycopy(head, 0, arrSum, 0, head.length);
// 7. 배열에 나머지 값들을 갖는 배열을 붙인다.
System.arraycopy(tail, 0, arrSum, head.length, tail.length);
// 8. 값들을 넣어준 배열을 반환한다.
return arrSum;
}으음... 코드로 봐도 이해가 어렵다..!!🤣
하나하나 순서대로 동작 순서를 봐보자!
동작 순서
arr = {1, 2, 3} 가 함수의 입력값으로 들어왔다면
reverseArr([1, 2, 3])
[1, 2, 3]의 크기가 0이 아니므로 [1, 2, 3]을 반환하지 않는다.
head에는 [1, 2, 3]의 마지막 값인 3이 저장된다.
tail에는 나머지 [1, 2]가 reverseArr를 실행하고 저장된다.
reverseArr([1, 2, 3])
head = [3]
tail =reverseArr([1, 2])
reverseArr([1, 2])
위의 tail에서 reverseArr([1, 2])가 실행되면
[1, 2]의 크기가 0이 아니므로 [1, 2]를 반환하지 않는다.
head에는 [1, 2]의 마지막 값인 2가 저장된다.
tail에는 나머지 [1]이 reverseArr를 실행하고 저장된다.
reverseArr([1, 2])
head = [2]
tail =reverseArr([1])
reverseArr([1])
위의 tail에서 reverseArr([1])이 실행되면
[1]의 크기가 0이 아니므로 [1]을 반환하지 않는다.
head에는 [1]의 마지막 값인 1이 저장된다.
tail에는 나머지가 없으므로 reverseArr([ ])가 실행되고 저장된다.
reverseArr([1])
head = [1]
tail =reverseArr([ ])
reverseArr([ ])
위의 tail에서 reverseArr([ ])가 실행되면
[ ]의 크기가 0이므로 [ ]가 반환된다.
드디어reverseArr([1])의 tail에 [ ] 배열이 저장된다.return [ ]
reverseArr([1])
reverseArr([ ])에서 [ ]를 반환받아서
head = [1]
tail = [ ]
인 상태가 되었다.
이제 tail을 선언하는 코드의 아래부분들이 실행된다.
새로운 배열을 만들어서 head를 앞에 넣어주고 tail을 뒤에 붙여준다.
arrSum = [1]
만들어진 배열을 반환한다.
reverseArr([1, 2])
reverseArr([1])에서 [1]을 반환받아서
head = [2]
tail = [1]
인 상태가 되었다.
새로운 배열을 만들어서 head를 앞에 넣어주고 tail을 뒤에 붙여준다.
arrSum = [2, 1]
만들어진 배열을 반환한다.
reverseArr([1, 2, 3])
reverseArr([1, 2])에서 [2, 1]를 반환받아서
head = [3]
tail = [2, 1]
인 상태가 되었다.
새로운 배열을 만들어서 head를 앞에 넣어주고 tail을 뒤에 붙여준다.
arrSum = [3, 2, 1]
만들어진 배열을 반환한다.
최종
위의 동작 순서를 한눈에 나타내자면 이렇다.
reverseArray([1,2,3])
head = [3]
tail = reverseArray([1, 2])
reverseArray([1,2])
head = [2]
tail = reverseArray([1])
reverseArray([1])
head = [1]
tail = reverseArray([ ])
reverseArray([ ])
return [ ];
길이가 3인 배열을 넣었는데도 이렇게 나타내기가 어렵다니 ㅠㅠ
실무에서는 재귀 함수를 사용하는 일은 잘 없다고 한다.
오히려 이해하기 힘든 코드를 작성하게되어 함께 일하는 사람들에게 욕을 한바가지 먹을수 있을것같다.(생명연장)
하지만 프로그래머로서 중요한 논리적인 생각을 하는 능력을 기를수 있고😎
취업에 코딩테스트라는 문턱이 존재하는 한 학습이 필요한 재귀 함수 였다!
잡소리
요즘 빠져있는 과자인 Potato Crisp이다.
너무 맛있어서 멈출수가 없엉..!!!
너무 좋아해서 군대에서 싼값에 질리도록 먹고 오자고 마음먹고 1일 1봉을 했던 포카칩 어니언맛 급으로 너무 맛있는 감자 과자를 찾아버렸다.
어디선가 1개씩 얻어서 쭈워먹었었는데 상자로 사서 먹으니 멈출수가 없는 중독성이 사람을 미치게만든다.
한봉지 까서 먹고나면 어느샌가 다른 한봉을 까고있는 내 자신을 발견할 수 있다.
먹고 돼지 돼야지.🐷
