[자료구조]재귀(Recursion)

어떤 문제가 있다고 가정하고, 이 문제를 동일 한 구조의 더 작은 문제로 나누어 작아진 문제를 해결함으로써 전체 문제를 해결하는 방법을 재귀 라고한다. 또한 사전적 의미는 "원래의 자리로 되돌아가거나 되돌아옴"이며,재귀를 사용한 코드는 간결하고, 이해하기 쉽다. 그밖에도 알고리즘 문제의 많은 부분을 차지한다.

 

자기자신을 호출하는 함수를 재귀함수라 한다 재귀 함수를 잘 활용하면 반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.

 

• 재귀함수의 장점

불필요하거나 여러개의 반복문을 사용하지 않기 때문에 코드가 간결하고 수정이 용이해진다

변수를 여러개 사용 할 필요가 없다.

 

• 재귀함수의 단점

반복문과 달리, 코드의 흐름을 직관적으로 파악하기 어렵다

반복하여 메서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장하게 된다. 이런 과정은 반복문에 비해 메모리를 더 많이 사용하게 된다.

메서드를 호출하고 메서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생하게 된다.

 

• 재귀함수를 사용하기 위한 조건

문제의 크기를 점점 작은 단위로 쪼갤 수 있어야한다.

재귀 호출이 종료되는 시점이 존재해야 한다.

 

반복문vs재귀

재귀가 적합한 상황

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

-중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운경우

-변수 사용을 줄여 mutable state(변경가능한 상태)를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우

 

학습 목표

• 재귀적으로 사고하는 법을 터득합니다.

• 재귀 함수의 입력값과 출력값 정의하기 

재귀 함수를 통해 풀고자하는 목표를 정의하는데 도움이 된다. 재귀적으로 사고하는 데에 가장 먼저 해야할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는것입니다. 함수arrSum의 경우 int타입을 요소로 갖는 배열을 입력으로 받고, int타입을 리턴합니다 >>>>>>>   arrSum: [int]->int 

• 문제를 잘게 쪼개어 사고하는 법을 활용할 수 있다.

문제를 어떻게 쪼갤지 생각하고 기준을 정한 후 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분 할 수 있는지 확인합니다. 일반적인 경우, 입력값으로 이 기준을 정합니다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기 입니다. 주어진 입력값 또는 문제 상황을 크기로 구분 할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 됩니다. 그리고 구분된 문제를 푸는 방식이 순서나 크기에 관계없이 모두 같다면 문제를 제대로 구분 한 것입니다.

-함수 arrSum의 경우 입력값인 리스트(배열)의 크기에 따라, 더 작은 문제로 나눌 수 있습니다. 그리고 arrSum(new int[]{1,2,3,4}를 구하는 방법과 arrSum(new int[]{2,3,4})을 구하는 방법은 동일하므로 적절하다고 판단 할 수 있다.

-함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있습니다. 각각의 경우는 다른 방식으로 처리해야합니다. 

arrSum : [number] => arrSum (int[]{}) / arrSum(new int[] {e1,e2,...en})

• 단순한 문제 해결하기

문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결합니다. 이를 재귀의 기초(base case)라고 부른다. 재귀의 기초는 재귀 함수를 구현할때 재귀의 탈출조건(재귀 호출이 멈추는 조건)을 구성합니다

-함수 arrSum을 더이상 쪼갤 수 없는 경우 입력값이 빈배열일 경우고, 이때 arrSum(new int[]{})의 리턴값은 0이다.

-arrSum: [number] => arrSum(new unt []{}) = 0 / arrSum(new int[]{e1,e2,...en})

• 복잡한 문제 해결하기

길이가 1 이상인 배열이 함수 arrSum에 입력된경우 맨 앞의 요소에 대한 결과를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라 칭하겠다),나머지 요소를 새로운 입력밧으로 갖는 무제로 구분하고 이를 해결하여 얻은 결과를 head에 더한다

-arrSum : [number] -> numberarrSum(new int []{}) =0/arrSum([e1,e2,...en]) = arrSum(new int[]{e1} +arrSum(new int[][e2,...,en])

-배열을 head와 나머지 부분(tail)으로 구분하는 방법만 안다면 함수 arrSum을 재귀적으로 구현할 수 있다.

• 메서드 자신의 재귀적 호출을 설명할 수 있다.
• 탈출 조건을 설정할 수 있다.

• 재귀 함수의 활용 (트리 구조)
  • JSON 구조에 재귀 함수를 활용할 수 있다.