_11_ 재귀(Recursion)

MJ Studio
알고리즘은 미친짓이다
8 min readMay 17, 2022

재귀 함수의 작동 원리와 주의할 점, 해결할 수 있는 문제의 예시들을 알아봅니다.

재귀(Recursion)

재귀는 뭘까요? 네.. 그냥 재귀함수라고 생각하면 됩니다. 자기 자신을 호출하는 함수이죠.

일반적인 개발에서 재귀함수를 쓸 일은 그리 많지 않지만 PS에서 재귀함수는 너무나 중요합니다. 그래서 많이 짜보면서 친해져야 합니다.

재귀함수가 쓰이는 대표적인 예시는 브루트포스, 백트랙킹, 다이나믹 프로그래밍, DFS, 여러 정렬, 그래프, 트리등 무궁무진 합니다. 대표적으로 예시를 들 수가 없네요…

사실 재귀함수를 이해하는건 어렵지 않지만 이런 알고리즘들을 배우며 재귀함수를 이렇게 짜면 이 알고리즘이 이렇게 동작하는구나! 하고 파악하는 과정이 더 중요하다고 생가각합니다.

재귀와 반복의 차이

여러 알고리즘들은 동일한 원리를 갖고 작동해도 구현을 재귀로 하느냐 다르게 하느냐로 구현법이 달라지기도 합니다.

이 두 구현법엔 대개 다음과 같은 차이점이 있습니다.

재귀(Recursion)

  1. 직관적이다. 함수 내부의 코드가 딱 하나의 step 에서 수행되어야 할 일만을 내포한다.
  2. 코딩의 난이도가 쉽다. 재귀 호출이 불리는 순서를 고려하지 않아도 되는 경우가 많다, 예외 케이스 처리도 쉽다.
  3. 느리다.
  4. 메모리를 많이 먹는다 — 함수가 계속 호출되면 스택 메모리에 쌓이게 되며 이는 손쉽게 메모리 초과로 이어지기도 합니다. 특히 파이썬에서 재귀 함수는 굉장히 느리고 언어 자체에 재귀 함수 호출 제한이 걸려있기도 해서 다음과 같이 재귀 함수의 호출 제한 횟수를 재설정한 뒤에 문제를 풀어야 하기도 합니다.
  5. 디버깅이 어렵다.

반복(Iteration)

보통 재귀가 가지는 특성과 반대입니다.

  1. 직관적이지 않다 — 보통 중첩 반복문을 통해 코딩이 이루어지고 따라서 어렵습니다.
  2. 순서를 고려해야 한다 — 예를 들어, 다이나믹 프로그래밍 문제를 푼다고 하면 배열의 어떤 인덱스부터 순서대로 채워지는지를 잘 확인해야합니다. out of index 에러도 더 유의해야 합니다.
  3. 빠르다.
  4. 반복문이기 때문에 함수를 호출해서 더 써야하는 메모리가 없다.
  5. 특정 경우 공간 복잡도가 더 적은 코드를 짤 수 있다 — 이는 토글링이나 슬라이딩 윈도우라고 부르는 기법인데, 예를 들어 1차원 배열만 선언해두고 이미 썼던 칸들이지만 이제 계산에 필요없어진 칸들을 다시 사용한다든지 하여 공간 복잡도를 아낄 수 있습니다. 실제로 이러한 특징을 이용해 반복문으로만 풀 수 있는 문제가 다이나믹 프로그래밍에선 나오기도 합니다(코테엔 안나옵니다).

이는 쉬운 알고리즘에 분류되는 DFS/BFS 같은 알고리즘부터 다이나믹 프로그래밍, FFT 라든지 어려운 알고리즘들까지 대개 공통적으로 적용되는 특징들입니다.

재귀만 쓸 수 있을 때가 있다

이론상(?)으로 모든 재귀함수는 반복문으로 대체가 가능하지만 역시나 시간/공간 복잡도에 큰 제약을 받지 않는 상황에서는 재귀 함수를 짜는 것이 편할 때가 매우 많습니다.

왜냐하면 코드 자체가 직관적이고 짜기 쉽기 때문입니다.

재귀함수의 시간복잡도

재귀함수를 사용할 때 헷갈리는 것 중 하나입니다.

우선 재귀 함수가 일반적인 상황일 때(특별한 인자여서 바로 종료(기저 조건)를 해주거나 하지 않을 때)의 함수의 시간복잡도를 따져보아야 합니다.

다음을 봅시다. 파이썬에선 전역 변수에 접근하려면 global 이라는 키워드로 표시를 해주어야 합니다.

Sum은 결국 10,000이 되었습니다. 왜인가요? 함수 한 번의 호출마다 100을 더해주고, 이는 시간 복잡도 O(100)이죠. 그리고 fn을 또 호출 할 때마다 i를 1씩 더해서 전달해주는데, 결국 in이 되면 멈추기 때문입니다.

i가 [0, 99]일 때 각 100번 씩 더해지므로 결국 Sum이 10,000이 됩니다.

즉, 이 함수의 시간 복잡도는 O(100n) 이라고 표현할 수 있습니다.

피보나치 수를 구하는 재귀함수를 보겠습니다.

이 함수의 시간복잡도는 뭔가요? 일단 n이 2이하인 특수한 경우는 함수가 O(1)만에 끝나버리기 때문에 일단 고려하지 않아도 됩니다.

그 이외에 케이스는 다른 동작은 하지 않고 n-1과 n-2를 호출해주는데, 이는 결론부터 말하자면 O(2^n) 입니다.

https://dev-ahn.tistory.com/144

왜냐하면 각 함수의 일반적인 동작에서 다른 재귀함수를 2번 더 호출하기 때문입니다. 물론 n-1뿐 아니라 n-2도 호출하기 때문에 정확히 O(2^n)번은 아니지만, 대략적으로 그렇다고 표현할 수 있습니다.

좀 더 복잡한 예시를 보겠습니다.

이 경우 우리는 checked 라는 전역 변수를 이용해 이미 어떤 i에 대해 계산이 되었다면(-1이 아니라면) 바로 O(1)만에 반환합니다.

만약 그렇지 않다면 fib(i — 2), fib(i — 1)을 호출하여 checked[i]를 채워주고 반환합니다.

이 경우 시간복잡도는 O(n)입니다.

일단 함수 내부에서 함수를 호출하고 뭔가를 검사하고 하는 과정은 모두 O(1) 입니다.

왜냐하면 fib(i-2)를 호출해도 거기서 일어나는 동작은 현재 진행되고 있는 함수에서 일어나는 동작은 아니기 때문입니다.

함수를 호출하는 시간복잡도도 O(1)이니까, 결국 O(1)이죠.

그리고 총 fib라는 함수가 n에 대해서 몇 번 호출되는지를 봐야 합니다.

만약 checked[i] 가 한 번 계산이 된 이후라면 fib(i)는 O(1)만에 종료되어 버립니다.

그렇지 않다면 checked[i]를 계산하는 동작도 O(1)이므로 결국 checked에 n개의 값만 계산이 된 이후에는 상관이 없어집니다.

따라서 전체 시간복잡도는 O(n)이 됩니다.

미리 눈치채신 분도 계시겠지만 이렇게 특정 값들을 미리 계산해두었다가 다시 사용하는 테크닉을 다이나믹 프로그래밍(Dynamic Programming)이라 하고 DP라고도 부릅니다.

PS에서 가장 중요하고 가장 많이 쓰이고 가장 난해하고 가장 변형도 많고 가장 짜증나고 할튼 개쩌는 알고리즘 분류 중 하나입니다. 추후에 천천히 즐겨보죠.

연습 문제

사실 재귀함수라는게 누구나 알 수 있지만 직접 문제를 풀며 몇 대 맞아보기 전까진 내 재귀함수 구현이 어디가 틀렸는 지 알기 힘듭니다. 실제로 몇 개 풀어볼까요?

재미있고 더러운 문제네요 한 번 봅시다.

fn 이라고 재귀함수 이름을 지었습니다. 전 함수 이름을 귀찮아서 저렇게 짓습니다.

재귀함수의 내부 동작을 결정하는 가장 중요한 요소는 인자입니다. 이 문제에선 depth라는 정수형 인자가 하나 들어옵니다.

인자를 보고 이 재귀함수의 동작을 결정해야 합니다. 항상 똑같은 인자가 들어오는 재귀함수는 말이 안됩니다. 만약 그렇다면 함수 호출이 무한히 이어져 재귀함수가 끝나지 않아 결국 스택에 끝없이 함수가 쌓여 메모리 초과가 나게 됩니다.

이 문제에서도 보면 함수 내부에서 함수를 호출할 때 현재 depth의 +1를 한 값을 전달해줌을 알 수 있고, depth가 n과 같아졌을 때 할 일을 하고 종료합니다.

우리가 브루트포스 알고리즘을 배웠는데, 재귀함수와 브루트포스 알고리즘을 같이 사용하는 문제 중 하나입니다.

물론 놀랍게도 permutation으로 그냥 해결할 수도 있습니다.

카드가 10장밖에 안되고 10!*10 이면 충분히 시간안에 돌아갈 시간 복잡도거든요.

실제로 그 코드는 다음과 같습니다. 코드가 조금 복잡한데 혹시 permutation을 복습 겸 다시 이렇게도 풀어보면 좋습니다. 정확히 말하자면 이 문제에서 이렇게 풀면 시간복잡도는 O(N * N!) 입니다. 해쉬셋의 시간복잡도를 O(1)이라고 가정했을 때에요.

이제 재귀로 풀어봅시다

일단 코드 투척합니다. 사실 짜다보니 좀 백트랙킹 같은 코드가 되어버렸는데 그냥 같이 설명해버리겠습니다.

여기서는 일단 used라는 배열을 사용합니다. 현재 n개의 수 중 어떤 것들이 이미 사용되었는지 아닌지를 표시해두는 배열입니다. 처음엔 모두 False 로 초기화가 되어 있습니다.

이제 set 이라는 녀석을 사용하는데, 문제에서 다른 방법으로 만들어도 같은 숫자가 된 것은 하나의 정답으로 본다고 했으므로 중복을 처리하기 위해 사용해 준 자료구조입니다.

fn의 인자 K는 현재 몇 개의 수를 더 이어붙여야 하는지를 나타냅니다.

가장 바깥쪽 호출문에서 문제의 입력인 k를 그대로 전달해주고 재귀 함수 내부에서 K0일 때 우리가 정답과 관련된 무언가를 해줍니다.

그리고 fn에서 fn을 호출 할 때 계속 K1씩 감소시키며 호출해주는 것을 볼 수 있습니다.

이제 K0이 아닐 때를 봅시다. n개의 수를 모두 보며 현재 사용된 수가 아닐 때만 현재 정답에 이어붙여주고 사용했다는 것을 True로 해줍니다.

그리고 이제 재귀함수를 호출해주고 이후에 무언가 설정해두었던 것을 그대로 돌려주기만 하면 됩니다.

이제 재귀함수가 모두 실행된 뒤에 answer_set 에는 정답 문자열들이 중복없이 담겨있고 이것의 길이를 출력하면 정답입니다.

--

--