[C언어] 재귀함수 개념 / 재귀함수 문제 & 설명

재귀함수란?

함수 내에서 자기 자신을 다시 호출하는 함수.

문제 : 자연수 N을 입력받아 1부터 N까지 출력을 하되 n-1번째 값은 n번째 값을 2로 나눈 몫이 되도록 하는 프로그램을 작성하시오.

#define _CRT_SECURE_NO_WARNINGS                // scanf 에러 방지
#include<stdio.h>

 
void list(int); 
void main()  
{
    int n;
    scanf("%d", &n);            // 자연수 N입력 받기       
 
    list(n);                    // list 함수 실행
}
 
 
void list(int n)                 // list 함수 
{
    if (n == 0)                  // n이 0일때 값을 반환하는 if문 = 재귀함수에서 빠져나오기 위한 조건
        return;
 
    list(n / 2);                 // 재귀 함수 (n을 나누기 2한 값을 넣는다.) 
    printf("%d ", n);            // 재귀 함수에서 빠져나오면 그동안 호출 스텍에 쌓여있던 값을 모두 출력
}

입력 예시 : 100 / 출력 예시 : 1 3 6 12 25 50 100

 

설명

1.  void list(int n)                 
2.  {
3.    if (n == 0)                 
4.       return;
 
5.    list(n / 2);                 // 재귀 함수 
6.    printf("%d ", n);           
7.   }

 

- 먼저, list 함수로 들어오게 되면 3번의 if문으로 간다.

 

- 3번 if문의 경우, n (입력받은 자연수 N)이 0일 때 값을 반환한다.

  -> 0이 아닌 값이 들어왔을 경우, 3번 if문을 지나쳐 5번의 함수로 진입한다.

  -> 5번의 함수는 자기 자신과 같은 재귀함수이다.

  -> 괄호 안의 수식대로 n의 값을 변형한다.

  -> 다시 1번의 함수로 진입하여 if문이 요구하는 조건을 충족 할 때까지 같은 과정을 반복한다. 

  -> 반복 중, n의 값이 0이 되어 if문의 조건에 충족하게 된다면 값을 반환하게 되며 재귀 함수에서 빠져나온다.

 

- 5번의 재귀함수에서 빠져나왔다면  6번으로 내려간다.

 

- 6번의 printf에서 지금까지 호출 스텍에 쌓인 n값을 역순으로 모두 출력한다.

  ->(100/50/25/12/6/3/1)순으로 쌓인 값을 (1/3/6/12/25/50/100)순으로 출력)

 

(문제출처 : JUNGOLhttp://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=131&sca=10d0 )