2/13 일일정리 재귀

재귀 알고리즘

출처 : 나무위키

 

재귀(recursion)함수란 자기 자신을 호출하는 함수를 말한다.

function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

위의 코드는 끝에 자기자신을 호출하여 무한정으로 console.log를 출력한다.

 

재귀로 문제 해결하기

문제 : 자연수로 이루어진 배열을 받아 각 요소의 합을 반환하는 arrSum 함수를 만들어보세요

 

⓵ 문제를 작게 쪼개기

[1,2,3,4,5] 라는 배열이 있을 경우 각 요소의 합은 (1 + [2,3,4,5] 배열의 각요소의 합) 과 같다.

이런식으로 문제를 비슷한 형태로 쪼개는 것을 코드로 나타내면 다음과 같다.

arrSum([1,2,3,4,5]) === 1 + arrSum([2,3,4,5])

arrSum([2,3,4,5]) === 2 + arrSum([3,4,5])

...

 

⓶ 문제를 가장 작은 단위로 쪼개기

위와 같은 방식으로 끝까지 문제를 쪼개면 다음과 같은 코드가 남는다.

arrSum([3, 4, 5]) === 3 + arrSum([4, 5])

arrSum([4, 5]) === 4 + arrSum([5])

arrSum([5]) === 5 + arrSum([])

 

⓷ 문제 해결하기

가장 작은 단위까지 문제를 분해했기 때문에 마지막에 남은 arrSum([])은 우리가 값을 지정해줘야 한다. arrSum([])의 값을 0으로 지정해주면 위의 코드와는 반대로 다시 하나씩 더해가게 된다.

function arrSum (arr) {
  //  가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length === 0) return 0;

  //  재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
  return arr.shift() + arrSum(arr)
}

출처 : 코드스테이츠

 

재귀를 사용하기 좋은 상황

⓵ 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

⓶ 중첩된 반복문이 많거나 반복 회수를 예측하기 힘든 경우

 

재귀의 장점과 단점

⓵ 장점

• 변수를 여러가지 만들 필요가 없다.
• 반복문을 사용하지 않기 때문에 코드가 간결해진다.

 

⓶ 단점

• 지속적으로 함수를 호출하게 되면서 함수를 계속 기억해야 한다. 반복문에 비해서 메모리를 더 많이 사용한다.
• 함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게 된다.
• 속도가 상대적으로 느린 경우가 있다.

여러 단점에도 불구하고 재귀를 사용하는 경우가 꽤 많다고 한다.

* 꼬리재귀 최적화(Tail Call Optimization)로 재귀의 단점을 극복할 수 있다.

 

 

재귀 사용 실습

코플릿 문제(알고리즘 문제)로 재귀함수 사용 실습을 해보았다.

개념이 어느정도 잡히니 재귀를 사용하는데는 큰 문제는 없었다.

 

간단한 덧셈, 곱셈, 피보나치 수열을 재귀함수로 구현하면서 기본 개념을 잡고, 배열뒤집기와 2차원 배열 펼치기를 재귀 함수로 구현해 보았다.

 

* 재귀함수를 호출할 때 return을 붙여줄지 아니면 그냥 부를지를 잘 판단해야 하는 것 같다.

* 배열관련으로 재귀함수를 만들 때 스프레드 문법을 많이 활용했다.