질문이 문제를 재귀함수로 구현이 가능한가 불가한가에 대한 판단 여부를 어떻게 결정할지에 대한 고민인가요?

단계가 명확히 정해져 있거나 논리(로직)가 명확하다면, 재귀함수를 사용 시 쉽게 구현이 가능하다는건 어렵지 않게 도출 할 수 있습니다.(다수의 문제는 재귀를 사용하지 않는 반복문으로도 충분히 구현이 가능합니다.)

다만 이 경우는 단계별로 작업할 내용이 명확하게 제시되어 있기 때문에 가능했던 것으로 보이며 직접 알고리즘을 고려하신다면 로직을 따라가지 않는 한 단계를 명확히 정의하기 어려울 것입니다.

우측의 식이 쉽게 도출됬던 것도 윗 답변분도 말하셨듯이 강사가 "로직을 돌려보지 않고 바로 도출"했던게 아니라 논리를 이해하고 단계를 명확히 정의했기 때문입니다. 또한 실제 사용 시 생각지 못한 문제가 발생할 수 있으니 기본적인 로직에 대한 이해를 갖추고 도구(코딩)을 사용하는걸 권해드립니다.

감사합니다.

재귀함수를 구현하는 방법은 우선 구현을 생각하지 않고, 문제를 해결하는 과정에서 현재의 문제와 닮은 꼴의 동일한 문제를 찾아내는 것입니다. 그리고 가장 단순한 문제에 대한 해답도 갖고 있어야 합니다. 이때 요령은 해당 문제가 이미 해결된 상태라고 가정하는 겁니다.

보통 이런 접근 방식을 수학적 귀납법이라 부르고 (Inductive Reasoning) 수학적 귀납법은 다음의 과정으로 이루어집니다.

1. 기반조건 p(0)이 참이다.
2. p(k) -> p(k+1) 가 참이다
3. p(n)이 참이다

말하자면 재귀함수는 1과 2를 통하여 3을 구현하는 함수입니다.

예를 들어서 n 팩토리얼 (1 * 2 * 3 * ... * n ) 을 구하는 재귀함수를 작성한다고 해봅시다.

n 팩토리얼의 정의는 1 * 2 * 3 * ... * n 입니다.

이는 (1 * 2 * ... * n - 1) * n 이고, (n-1 팩토리얼) * n 입니다.

솔루션을 구하는 과정에서 동일한부분 문제를 발견하였습니다.

그리고 가장 단순한 문제인 1 팩토리얼의 값은 1입니다.

함수를 f라고 하면 다음과 같이 쓸 수 있습니다.

f(n):
  if (n == 1) return 1
  return f(n-1) * n

하노이탑 문제로 넘어가 봅시다.

하노이탑은 쌓여있는 원판을 다른 기둥으로 옮기는 문제입니다.

a, b, c 세 기둥이 있고 원판은 편의상 아래처럼 배열로 표기하겠습니다.

[1, 2, 3, 4], [], [] 크기 1, 2, 3, 4의 원판이 첫 번째 기둥에 있는 예를 들겠습니다.

우리는 이미 n개의 하노이탑을 a에서 c로 옮기는 방법을 안다고 가정 합니다. 그건 f(n, a, b, c)입니다.

자 그러면 위 문제를 [1, 2, 3], [] [] 만 놓고 생각하면 기둥 b, 기둥 c로 옮길 수 있겠죠? 즉,

[1, 2, 3, 4], [], [] -> [4] [1, 2, 3] [] : f(3, a, c, b)

[1, 2, 3, 4], [], [] -> [4] [] [1, 2, 3] : f(3, a, b, c)

근데 c로 옮기면 안 됩니다. c에는 4가 깔려야 하거든요.

그래서 [1, 2, 3]을 우선 기둥 b로 옮긴다음 4를 c로 옮겨야 합니다.

[4] [1, 2, 3] [] -> [] [1, 2, 3] [4] : 1 (이 값은 f(1, a, b, c) 와 같습니다 )

[] [1, 2, 3] [4] -> [] [] [1,2,3,4] : 1 + f(3, b, a, c)

즉 f(4, a, b, c) = f(3, a, c, b) + 1 + f(3, b, a, c) 입니다.

질문자분이 의문을 품는 부분은 이렇게 구한 식입니다.

위 예시에서는 4를 예시로 들었지만 n으로 표현하면

f(n, a, b, c) = f(n-1, a, c, b) + 1 + f(n-1, b, a, c) 입니다.

그럼 기반조건을 찾아봅시다. f(1, a, b, c) = 1 입니다. (명백하죠?) 이제 이걸 코드로 써보면 다음과 같이 됩니다.

f(n, a, b, c):
  if (n == 1) return 1
  return (
    f(n-1, a, c ,b) +
    1 +
    f(n-1, b, a, c)
  )

재귀 함수는 하고자 하는 동작의 재귀적인 특성을 파악한 후에 그것을 함수로 만들면 됩니다. 일반적인 함수들은 코드의 흐름을 위에서 아래로, 왼쪽에서 오른쪽으로 쫓아가면서 분석하는 경우가 대부분인데요. 유일하게 재귀함수는 그 흐름을 쫓을 필요도 없고, 쫓아가면서 생각할 경우 그 단계가 깊을수록 전혀 이해가 안가버리는 경우가 대부분입니다.

재귀 함수는 재귀적인 동작을 하는 것들, 예를 들어, 피보나치 수열, 팩토리얼, 하노이 타워, 트리의 순회 등에서 주로 사용됩니다.

보통 나좀 짠다고 생각하는 분들도 재귀함수를 처음에 잘 이해 못하는 경우가 있는데 아마도 기존의 코딩 고정관념을 가지고 이해하려고 해서 그런거 같아요.

질문하신대로 식을 도출해서 그 식대로 함수를 짜고, 그 함수가 몇몇 테스트에서 잘 동작한다면 흐름을 구지 생각안하셔도 되요. 흐름을 처음 학습 단계에서 한번정도 검토해 보는 것은 좋지만 2번 이상 검토할 필요는 절대 없습니다.

재귀 함수는 함수 내에서 자기 자신을 쓰면 재귀 함수이지만, 실용적인 재귀 함수가 되기 위해서는 2가지 조건이 필요합니다. 하나는 재귀 함수로부터 탈출할 수 있는 탈출 조건이 반드시 필요하고요. 두번째는 재귀 함수 내부에서 다시 자기 자신을 호출할 때, 호출시 인수가 함수의 매개변수와 달라야 합니다. 그래야만 언젠가 탈출 조건이 성립될 수 있습니다. 이 두가지가 사용할 수 있는 재귀 함수의 특징이고, 어떤 재귀함수든 다들 이 두가지를 만족할 거에요.

재귀함수가 이해되기 전까지는 "이게 먼소리지?" 막 이럴수 있거든요. 그런데 이해 되고 나신 후에는 "별것도 아니네." 이런식으로 마음 편해지실 거에요.

너무 코드의 흐름 쫓아가면서 분석하지 마시고, 고정관념 버리시고, 인터넷 글이나 책에서 설명하는 대로 식을 먼저 세우시고 그걸 그대로 코드로 만들면 됩니다. 재귀적인 식을 만들 수 있다면, 그것을 그대로 코드로 만들수 있다는 것도 재귀 함수의 장점입니다.

재귀함수는 잘 사용하면 프로그램의 속도를 높일수도 있고요. 잘못 사용하면 반대로 속도가 느려지기도 합니다. 또한, 재귀함수를 모르면 절대 해결할 수 없는 하노이 타워나 트리의 순회 같은 것들도 있어서 익숙해지면 좋습니다.