재귀적 호출(순환 호출) 함수의 이해와 예제, 문제 -C언어

재귀적 호출 함수를 이해하기 위해선

사용자 정의 함수를 먼저 알고있어야 합니다.

(잘 모르신다면 아래 글을 참고해주세요.)

'사용자 정의 함수의 이해와 예제, 문제 -C언어'

이번에는 재귀적 호출 함수에 대하여 알아보도록 하겠습니다.

 

재귀적 호출 함수란 무엇일까요?

 말그대로 재귀(再歸 : 원래의 자리로 되돌아가거나 되돌아옴) 함수입니다.

 함수에서 다른 함수를 호출하는 게 가능하다는 걸 알고 계시죠?

 여기서 달라지는 부분이 바로 다른 함수를 호출하는 것이 아닌

 자기 자신을 다시 호출한다는 것입니다.

Recursive라는 함수를 만들어 예를 들어볼까요?

void Recursive(){

    //내용

    Recursive();

}

같은 식으로 구성된 함수입니다.

이런 함수를 메인에서 ( int main(void) { Recursive(); return 0; } )

한번 호출한다면 어떻게 될까요?

아마도 main -> Recursive() -> Recursive() -> ... -> Recursive() -> ...

이렇게 되겠죠?

끝도 없이 함수 Recursive()가 반복하여 호출될 겁니다.

단순히 반복하여 계속 호출된다면 의미가 없겠죠? 무한 루프나 다름 없으니까요.

그래서 다시 자신을 호출하는 함수는 특정 조건을 가지고 반복되어야 합니다.

그럼 실제 예제 소스와 실행 결과로 확인해볼까요?

예제1. 단순히 "함수 호출됨"이라는 글을 계속 반복 출력하는 프로그램입니다. 한번 글이 출력될 때마다 일시 정지를 해주고 재귀 호출 함수로 구성하도록 합니다.

(소스)

 

자, 이렇게 Recursive() 함수는 main에서 한 번 호출됩니다.

Recursive() 함수에서는 printf()로 출력을 한번 해준 후 다시 Recursive() 함수를 호출하고요.

여기서 system("PAUSE");를 모르고 계신다면 잠깐만 어떤 기능을 하는지

아래 글에서 확인하고 예제를 계속 보시면 좋을 것 같네요.

'프로그램 일시정지, PAUSE -C언어'

(실행 결과 1 - 실행하고 바로)

(실행 결과 2 - 실행하고 아무 키나 입력)

(실행 결과 3 - 실행하고 아무 키나 입력 여러 번)

자 출력 결과를 보니 어떻게 돌아가는지 아시겠나요?

메인에서 Recursive() 호출 - 내용인 printf로 출력 - 일시정지 - 다시 Recursive() 호출이 반복되는 상황인 거죠?

이렇게 함수에서 다시 자신을 부르는 함수를 재귀적 호출 함수라고 합니다.

그럼 예제 2번!

예제 1번의 소스를 약간 바꿔서

아래와 같이 변경하여 실행하면 어떻게 될까요?

(소스)

(재귀(순환) 호출)함수 내부에 변화가 생겼죠?

(인수를 하나 받아오고 재귀 호출 때 또 전해주죠?)
이렇게 어떤 특정 조건이 붙어 함수가 그 조건에 따라서 반복 실행이 되도록 만듭니다.

어떤 결과가 나올 것 같나요?

한번 생각해보신 후 아래를 확인해보세요.

(실행 결과)

왜 이렇게 실행됐는지 아시겠나요?

cnt가 점점 줄어가기 때문이죠? 다시 호출될 때마다 1씩 줄어가

1보다 작아지는 때까지 계속해서 재귀 호출이 일어나게 되는거죠?

( 여기서 void 함수에서 return;을 만나면 함수를 중간에 종료하게 됩니다. 반복문의 break와 유사)

그렇다면 여기 main 함수에서

Recursive(5);를 Recursive(3);으로 바꾸면 어떤 결과가 나올 것 같나요?

(소스)

어떤 차이가 생길지 감이 오시죠?

실행 결과를 확인해볼까요?

(실행 결과)

생각한 대로 출력 결과가 나왔나요?

 

그러면 마지막으로 하나만 더 봅시다.

재귀 호출을 응용하여 많이 사용되는 방법입니다.

예제3. 숫자 n을 입력받아 1부터 n까지 더하는 재귀적 호출 함수를 작성하여 실행하시오. (반복문 사용x)

 라는 프로그램을 만든다고 할 때, 어떤 소스로 어떤 결과가 나오는지 확인해볼까요?

(소스)

이번에도 소스를 먼저 확인하고

소스가 어떤식으로 실행되는지 이해하도록 합니다.

실행이 어떤식으로 되는지

어떻게 재귀호출이 될 것 같나요?

가장 핵심인

 return n + Recursive(n-1);

이 부분이 어떻게 실행되어 결과가 나올 것 같나요?

일단 실행 결과를 보시죠.

(실행 결과)

이렇게 실행 결과만 봐서 정확히 어떤 구조로 실행되는지 아시겠나요?

처음으로 재귀적 호출 함수를 배운다고 생각하고 그림으로 설명하겠습니다.

(이런 구조도 이해하고 쓸 수 있다면 좋겠죠?)

순서대로 보자면..

처음 Recursive(3)이 호출되면

리턴으로 3+Recursive(2)를 반환하려고 합니다.

이 때, Recursive(2)의 값을 알기 위해 Recursive(2) 함수를 호출합니다.

Recursive(2)가 호출되면 반환(return) 값으로 2+Recursive(1)을 반환하려고 합니다.

이때도 마찬가지로 Recursive(1)의 값을 알기 위해 Recursive(1) 함수를 호출합니다.

Recursive(1)은 1을 반환하겠죠?

그러면 이제 다시 위로 돌아가며 값을 얻은 결과를 반환해주면 됩니다.

정리해보면,

Recursive(1) = 리턴 1

Recursive(2) = 2 + 1(Recursive(1)의 결과)

Recursive(3) = 3 + 3(Recursive(2)의 결과)

이렇게 Recursive(3)은 6이라는 값을 반환하는 것입니다.

어떤 방식으로 진행되는지 아시겠나요?

그럼, 이제 문제들을 풀어보며 재귀 호출 함수는 어떻게 사용하는지,

어떠한 경우에 사용되는지 확인해봅시다.

 

 

문제1. 구구단 중 출력을 원하는 단을 입력받아, 해당 단을 재귀 함수를 이용하여 출력하시오. (반복문 사용X)

(출력 결과 예)

인수로 현재 원하는 단의 값 dan과 카운트를 해줄 n 두 가지를 전달했습니다.

재귀 호출을 하며 이 n부분이 1씩 증가하고 결국 9까지 출력한 후에는 재귀 호출이 안 되게 되었습니다.

이런 방법으로 원하는 단을 출력하는 재귀적 호출 함수로 만들어줬지만,

다른 방법도 있겠죠?

문제2. 팩토리얼의 결과 값을 재귀 함수를 이용하여 구하시오.(반복문 사용X)

 (Factorial은 1부터 n까지 곱한 값입니다. 단 예외로 0!은 1입니다.

  1! = 1, 2! = 1x2, 3! = 1x2x3, 4! = 1x2x3x4 입니다.)

(출력 결과 예)

factorial의 경우 0!, 1!은 1이고, 2! = 1*2, 3! = 1*2*3 같은 결과가 나와야겠죠?

 전달 받은 인수인 f가 1보다 큰 경우

 '현재 수 x (현재보다 1 작은 수의 팩토리얼 함수)'를 호출하죠?

지금까지 재귀적 호출(순환 호출) 함수에 대하여 알아봤습니다.

 

재귀 호출을 할 필요가 있다고 생각되면 재귀 호출 함수도 만들어서 사용하실 수 있겠나요?

다른 예제도 재귀 호출 함수로 만들어 본다면 연습에 도움이 될 것 같네요!

'재귀적 호출 함수'가 어떤 것인지부터 예제를 통하여 설명을 듣고 이해하며, 직접 문제까지 풀어봤습니다.

'재귀적 호출 함수' 이해에 도움이 됐다면 좋겠습니다.

 

질문은 댓글이나 메일로 따로 연락주시면 시간되는 때 답변드리겠습니다. ( 연락 )