재귀 함수란? (recursive function)

재귀 함수는 말그대로 자기 함수를 호출하는것을 의미한다.

 

이해하기 쉽도록 코드로 설명을 해보면

function recursive(variable) {
    ...
    ...
    if(조건 충족){
        return result;
    } else{
        return recursive(value);
   }
}

이런식으로 while 문처럼 무한 반복이 아닌 종료 조건이 있는 전제 하에 자기 자신을 호출하는 함수이다.

대표적으로 재귀함수로는 하노이 탑이 있다.

하노이 탑은 타워 1에서 타워 3으로 그대로 탑을 옮기면 되는데 단 조건이다.

작은판 위에 큰판을 올릴수가 없는것이고 한번에 하나씩만 옮길수가 있다.

직접적으로 만들어서 해봐도 좋고 머리로 생각을 해봐도 좋은데 결국엔 하는 행동이 반복적이게 된다.

결론은 가장 아래있는 판은 목적지로 옮겨야하고 그러기 위해서는 그전에 가장마지막꺼를 제외한 모든것은 목적지 말고 다른 곳으로 옮겨야한다는게 반복이 된다.

 

물론 이런 재귀함수들은 대체적으로 반복문으로 처리가 가능할수도 있다.

재귀를 사용하면 스택을 사용하게 되어 메모리에 부하가 걸리는것도 단점이다.

그러나 왜 재귀를 사용하게 되냐면 만약에 배열 안에 있는 값들의 총 합을 구한다고 해보자

[1,2,3,4,5] 처럼 간단하다면 반복문으로 가능하겠지만 만약 숫자가 아닌 그 배열 안에 배열이 들어있을수도 있고 또 그배열안에 새로운 배열이 들어있을수도 있다.

그럴경우엔 배열의 길이가 0 이 될때까지 더하고 넘어가는 작업이 필요하다.

이런것도 반복문으로 가능은 하지만 재귀함수로 구현을 해야 더욱 깔끔한 코드가 된다.

 

여담으로 재밌는 궁금증이 있었는데 예전에 리눅스 라이선스 관련해서 다룬적이 있긴한데 라이센스에 대해서 처음 공부할때 얘기이다.

GNU 라이센스라는게 있는데 GNU의 뜻은 GNU's Not Unix 라는 뜻이다.

GNU가 뭐의 약자인지 보니 GNU는 유닉스가 아니다 라는 약자를 갖고 있다.

리눅스라는것을 알리기 위해 이런건 알겠는데 GNU를 모르기에 계속해서 파고 들어가도 결국엔 GNU's Not Unix 라는 값 밖에는 도출할수가 없다.

이것도 재귀의 일부인가 라는 생각도 한적이 있었다 :)