[알고리즘] 재귀함수

재귀는 재귀 (원래의 자리로 되돌아가거나 되돌아옴)

어떻게 보면은 무한 반복문과 굉장히 비슷합니다. 살면서 재귀라는 말을 듣기 어려운거 같은데 쉽게 생각하면 반복문과 다를게 없습니다. 특히 무한 반복문 while이나 재귀함수나 탈출 조건을 if문으로 설정 해주어야 하는 것 처럼..

항상 느끼는 거지만, 어렵게 생각하면 한없이 어려운 것 같습니다. 그렇기 때문에 많이 해보아야 해결 되는 문제인듯 합니다.

 

재귀를 사용할 때

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

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

 

 

ex) 펙토리얼 재귀함수

function fac(n){
	if(n===1){    // 탈출 조건
    return 1;
    }
    return n * fac(n-1)  // 자기 자신을 부르는 재귀함수 fac(n-1)
  }

 

펙토리얼 재귀함수 그림으로 표현

 

재귀적으로 사고하기

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

재귀 함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는 데 도움이 됩니다. 재귀적으로 사고하는 데에 가장 먼저 해야할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것입니다.

2. 문제를 쪼개고 경우의 수를 나누기

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

3. 단순한 문제 해결하기

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

4. 복잡한 문제 해결하기

남아있는 복잡한 경우를 해결합니다.

결국 수도코드를 잘잘 작성 해야 되는 뜻 입니다.

 

결론은

반복문은 함수의 한 부분을 반복하는 반면에, 재귀 함수는 자기 자신을 다시 한번 더 반복하게 됩니다.

수도코드 작성을 하면 굉장히 쉬워지고 그럼에도 어려우면 많이 반복하여 익숙해지는 수 밖에 없습니다.

코플릿을 푸는시간을 많이 가졌는데 결국은 많이 풀어보면서 적응해야 한다는 점 입니다.