[재귀함수] 재귀함수 구현할 때 염두에 두면 좋은 것들

 

 

 

 

 

 

 

작년에 c언어를 처음 배울 때도 재귀함수에 대해서 배웠는데 너무 어려워서 그냥 무시한 적이 있었는데

물론 그랬다가 지금 충분히 고통을 받을 수 있었습니다.

 

 

그래서 재귀함수와 함께 지지고 볶고 하다가 결국 여러가지를 깨달을 수 있었습니다..

아직 저도 제대로 아는건 아니지만 발상하는 방법 자체를 정리하면 좋을 것 같네요!

 

 

 

 

 

 

---

발상에 도움되는 것

---

 

일단 재귀함수를 어려워하는 사람들의 특징은(나도그랬고)

재귀가 일어나는 안쪽에서 어떻게 진행이 되는가

에 대해서 궁금해한다는 것입니다..

물론 알면 좋겠지만, 재귀가 3중, 4중으로 겹겹이 진행되면 머리가 슬슬 아파오고, 포기를 하게 됩니다.

 

 

그러나 재귀함수에서 진짜 핵심은

재귀함수를 사용함으로써 재귀함수가 하는 역할

을 파악하는 것입니다.

 

우리가 굳이 재귀함수를 다 헤쳐보았을 때 어떤 일을 하는지에 대해서는 궁금해 할 필요가 없어요.

어차피 컴퓨터가 해주는 일인데 굳이 궁금해 할 필요는 당연히 없습니다.

 

 

 

나는 결론적으로 재귀함수는 수학적 귀납법과 같은 원리라는 글을 보았을 때 완벽하게 이해했습니다.

 

수학 관련 용어가 나왔다고 소스라치지 말고, 조금만 참아봅시다.

 

우선 수학적 귀납법은 다음과 같은 흐름으로 진행됩니다.

 

 

 

1) n=1일때 명제를 증명한다.

2) n=k일때 명제가 성립한다고 가정한다.

3) n=k+1일때 명제가 성립함을 2)를 이용해 증명한다.

 

 

 

여기서 핵심은 n을 모든 자연수에 대해서 일일히 증명하지 않고, n=k일때 성립한다고 가정해버린 후

n=k+1일때 명제가 성립함을 2)와의 관계를 이용해 증명한다는 것이죠.

재귀함수를 공부할 때 재귀함수 안에서 일어나는 일을 이해하려고 하는것은

n이 모든 자연수일때를 다 대입해서 이해하려는 것과 같다는 것입니다.

 

 

 

따라서 재귀함수도 같은 원리로 이해하면 편합니다.

 

 

 

1) n=1(초기값)에 대하여 함수안에 식을 구현해 놓는다.

2) n=k일때 함수가 성립한다고 가정한다.

3) n = k+1일때 n=k일때와의 연관성을 탐구한 후 코딩을 한다.

 

 

 

이때 재귀함수와 수학적 귀납법의 차이점은

 

재귀함수를 작성할 때는 3)에서 분기문이라던가, 부수적인 코딩을 생각해주어야 한다는 정도입니다.

언제까지나 기본 원리가 같다고 했으니 참고만 해도 좋을 것 같습니다.

 

 

 

 

근데 막상 이해하면 편하긴한데

이 재귀함수 방법이 실행시간을 어마어마하게 잡아먹는 아이이다...

기본적으로 반복문과 함수호출은 실행시간 길어지는 주범인데,

재귀함수는 보통 둘다 가지고 있는지라 정말 기하급수적으로 길어집니다.

 

 

 

물론 한번쯤은 이해해서 나쁠건 없지만

그냥 한번쯤....그 이상은 그닥...