알고리즘 공부 - recursion

안녕하세요. yeTi입니다.
오늘은 알고리즘 강의의 시작인 recursion 에 대한 정보를 공유하고자 합니다.

의문

강의를 시작하면서 다음과 같은 의구심이 들었습니다.

• 알고리즘을 공부하는데 왜 recursion 부터 시작할까??
• 문제를 푸는 방식에 대한 강의가 중요한거 아닌가??

문제의 부분화

Recursion 은 프로그래밍에서는 재귀함수를 표현하는 의미로 쓰입니다.

Recursion 은 문제를 해결하는 범위를 축소시키는 사고를 하기위한 방식이라는 느낌을 받았습니다.

예를 들어, 다음과 같은 문제가 주어진다면

주어진 n개의 수들에 총합을 구하라

직관적인 해결책은 절차적인 방식으로 반복문을 활용하여 n 회 반복하며 모든 수의 총합을 구하는 방식입니다.

하지만 recursion 을 활용하면 다음과 같이 사고할 수 있습니다.

n-1개의 총합에서 n을 더한다.

이러한 사고의 차이는 검증에 대한 차이도 발생합니다.

검증의 논리화

앞서 문제에서 다른 두 개의 해결 방식을 확인했습니다.

문제:

주어진 n개의 수들에 총합을 구하라

해결책 1:

반복문을 활용하여 n 회 반복

해결책 2:

n-1개의 총합에서 n을 더한다.

해결책 1 을 검증하기 위해서는 입력 조건의 다양성을 가지고 검증하는 방식을 취해야합니다.

따라서 모든 경우의 수를 검증하기란 불가능한 구조입니다.

반면, 해결책 2 는 수학적 귀납법 에 의거해 논리적 타당성을 증명합니다.

논리적으로 타당하니 논리내의 모든 경우의수는 옳은 답을 반환한다고 검증할 수 있습니다.

필요성

알고리즘을 공부해야하는 이유 도 사실 recursion 의 명료함에 충격을 받아 작성하게 됐습니다.

그만큼 recursive thinking 이 문제의 해결관점에서 보다 명료한 시각을 전달해주는 경우가 있기 때문에 그리고 그 검증 또한 논리적으로 명료하게 수행할 수 있기 때문에 필요하다고 생각합니다.

규약

Recursion 을 사용하기 위해서는 간략한 규약이 있습니다.

하나 이상의 Base case 가 반드시 존재해야하고, recursive case 는 base case 로 수렴해야 한다는 것입니다.

그리고 명시적 매개변수 를 활용해야 합니다. 즉, 임의로 정의한 범위값을 활용하는 것 보다는 명확하게 범위값을 외부에서 제공할 수 있도록 하는것이 좋다는 의미입니다.

응용 문제

• 미로찾기
• Counting Cells in a Blobhttps://github.com/amansman77/study-algorithm-koh/blob/main/com/ho/study/algorithm/koh/recursion/CountCells.java
• N-Queens : Backtracking, DFS
• Powerset
• Permutation

관련 글

• 알고리즘을 공부해야하는 이유