재귀호출

재귀호출(Recursive call)

함수 안에 함수를 부르면 어떻게 될까? Caller(함수를 호출하는 함수)와 Calllee(호출되는 함수)가 같게 될 수가 있냐면, 가능하다. 재귀호출은 반복문에서 Stack을 더한 것과 일치한다. 논리구조는 반복문이고, 자료구조에 Stack이 합쳐진 경우다.

재귀호출도 반복문이기 때문에 반복횟수가 중요하다. 그냥 반복이 안 끊어지게 코드를 짜면 무한루프를 타다가 프로그램이 죽어버린다. 그러기에 반복문의 형식을 챙겨줘야 된다.

첫 번째로, 계수의 부분은 ‘함수이름‘(값);으로 할 수 있다. 이 경우, 값이 바로 인수가 돼서 함수가 스스로 호출되기 때문에 이때 반복이 생긴다. 여기서 값을 ++,--로 증감연산자를 붙여서 계수를 해줄 수 있다.

두 번째로, (조건식)반복횟수는, if(‘매개변수’ <= 0)등과 같은 조건식으로 성립한다면 return;을 해줘서 함수를 끝내면 된다. 마지막으로, 조건식에 들어가는 변수는 이미 매개변수가 있다. 이렇게 반복문의 3가지 형식을 구현할 수 있다.

 

재귀호출의 특이한 점

이렇게 재귀 호출하는 함수 안에 계수와 조건식, 변수까지 짜여졌다. 그리고 이것들을 뺀 나머지 실행문은, 반복문의 함수 바디(스코프{ })안에 있는 것처럼 되는데, 만약 계수역할인 ‘함수이름‘(값);과 실행문의 순서가 바뀌면 어떨까?

반복문 에서는 그러든지 간에, 함수가 끝난 다음 반복돼서 조건식으로 올라가는 것이 변함없지만, 재귀호출은 다르다. ‘함수이름‘(값);자체가 함수의 호출이기 때문에 이걸 만나면 goto()문처럼 함수의 윗부분으로 올라가게 된다. 그래서 실행문 위에 이 함수의 호출이 있게 되면, 실행문은 실행되지 않고 함수가 반복하다가 조건식에 걸려서 return;을 만나면 한 번에 터져 나온다.

영상의 예제와 같이 printf로 수와, 그 수의 주소를 출력하게 돼있으면, 차례차례 출력이 되는데, 최근에 쌓인 것부터 실행되는 것이다. 김치냉장고의 맨 아래 김치 통을 해결하려면 그 위에 쌓인 김치 통부터 차근차근 꺼내야 되듯이 말이다. 재귀호출 한 함수는 자료구조가 스택이라, 메모리를 그리면 알 수 있듯이 아래서부터 반복된 함수가 차곡차곡 쌓인다. 그래서 반환할 때 위의 실행문부터 차근차근 되는 것이다.(여기서 헷갈리지 말 것은, while같은 반복문과 다르게, 함수가 겹쳐서 있는 상태다. 하나만 출력되고 끝나는 것이 아닌 점이다.)

이렇게 보면 반복문보다 간결하게 프로그램을 짤 수도 있다. 그러나 고려해야 될 점은, 이 함수가 5개 쌓이는 것이 아닌, 500개가 쌓인다고 하면, 순간 사용하는 메모리(스택)이 엄청 많게 되고, 함수 호출이라서 속도가 느린 단점이 있다.

그래도 파일시스템(폴더)이나 트리 형태의 자료구조를 다룰 때 아주 유용하게 쓰인다.(그 때 빼곤 반복문을 쓰는 것이 좋다)