[알고리즘] 재귀란, 느낌으로 이해하기

알고리즘 문제를 풀다가 재귀를 활용하는 방법이 어렵고 흥미로워서, 저처럼 재귀를 처음 접하며 혼란스러운 사람들에게 조금이나마 도움이 되고자합니다.

 

우선 제가 어렴풋이 느꼈던 재귀란 대충 이러합니다.

 

재귀는 같은 로직으로 조금씩 나누어 해결하는 것.
그리고, 나는 '초기값'과 '조금씩' 집중하고 나머지는 믿고 맡기는 것.

 

 

예를 들어 설명해보겠습니다. 

아주 간단한 예시로는 피보나치 수열이 있습니다.

 

피보나치 수열은 이렇게 표현하죠.

Fn = F(n-1) + F(n-2) ( F1 , F2 = 1)

N번째 항은 이전 두 항을 더한 값이다.

 

n-1, n-2번째 항을 구하기 위해서는 또 그들의 이전 값들을 더하고 또 더하는 것을 반복해야합니다.  즉, 같은 로직이 반복되고 있습니다.

그리고 중요하것은 이것입니다. '초기값'과 '조금씩'에 집중하고 나머지는 믿고 맡긴다. 예를 들어 우리는 20번째 항을 정확히 알지는 못해도, 19번째 항과 18번째 항의 합이라는 것을 알고 있고 1번째와 2번째 값이 1이라는 것을 알고 있습니다. 그리고 그것으로 꽤나 정확하다고 생각하며 만족합니다. 이 태도가 우리가 재귀를 쓸 때 가져야하는 마음가짐이라고 생각합니다.

 

이 수열을 구현한 아래 코드로 잘펴보죠.

int fibo(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 1;
    } else {
        return fibo(n-1) + fibo(n-2);
    }
}

처음 재귀를 접한 저 같은 사람들은 이렇게 생각합니다.

'fibo(n-1)이 뭐지? 매개 변수로 n-1를 넣어줬으니까,,, 그럼 fibo(n-2)은,,,그럼 fibo(n-3)은,,,'

그러다가 n에 좀 큰 값을 넣어버리면 머리가 터질 것 같아집니다. (저의 머리는 stack size가 작은 것 같습니다 ㅠ)

 

여기서 하나의 팁은 저 로직의 고민을 n부터 시작하지말고 1부터 시작하는 것입니다.

'아 저 로직이 계속 반복되다보면 결국 fibo(1)까지 내려가겠네? fibo(1)은 1이고, fibo(2)는 1이네? 오 그럼 fibo(3)은 2 겠구나!'

어떤 재귀든, 차근 차근 1층까지 내려가지말고, 일단 1층으로 뛰어내린다음에 올라가면 이해하기가 한결 수월합니다.

 

이런 고민들을 하다보면 이제야 재귀가 조금 보입니다.

'아 초기값이 1이고 이전 두 값을 더하는 거구나'

정확한 마지막 값까지 머리로 따라갈 수는 없어도, '초기값'과 '조금씩의 로직'만 믿고 만족합니다. 

 

여기까지 재귀에 대한 부족한 설명이었습니다. 막상 쓰고 나니 별 게 없지만, 조금이라도 도움이 되길 바랍니다.