Algorithm(1): Recursion Ft

Tail Recursion(꼬리재귀)

void recurse(int n)
{
  if (n == 0)
    return;
  else
  {
    printf("%d ",n);
    recurse(n-1);
  }
}

int main()
{
  int num;
  printf("Enter a number: \n");
  scanf("%d", &num);
  recurse(num);

  return 0;
}

Head Recursion(머리재귀)

void recurse(int n)
{
  if (n == 0)
    return;
  else
  {
    recurse(n-1);
    printf("%d ",n);
  }
}

int main()
{
  int num;
  printf("Enter a positive integer: \n");
  scanf("%d", &num);
  recurse(num);

  return 0;
}

머리 재귀함수 설명

재귀 함수의 작동 과정 (스택을 사용한 실행 흐름)
재귀 호출은 함수 호출 스택(Call Stack)을 사용하여 작동합니다. 이를 입력 n = 5로 실행해보며 추적해 보겠습니다.

1. 첫 호출 recurse(5):
   조건 n == 0이 거짓이므로 recurse(4) 호출.
   스택에 recurse(5) 대기.

2. 두 번째 호출 recurse(4):
   조건 n == 0이 거짓이므로 recurse(3) 호출.
   스택에 recurse(4) 대기.

3. 세 번째 호출 recurse(3):
   조건 n == 0이 거짓이므로 recurse(2) 호출.
   스택에 recurse(3) 대기.

4. 네 번째 호출 recurse(2):
   조건 n == 0이 거짓이므로 recurse(1) 호출.
   스택에 recurse(2) 대기.

5. 다섯 번째 호출 recurse(1):
   조건 n == 0이 거짓이므로 recurse(0) 호출.
   스택에 recurse(1) 대기.

6. 여섯 번째 호출 recurse(0):
   조건 n == 0이 참이므로 return 실행.
   스택의 가장 위에서 recurse(0) 제거.
   호출이 끝난 후 스택이 처리되는 과정 (거꾸로 출력)
   이제 호출이 끝났으므로, 스택에서 하나씩 함수가 제거되면서 출력문 printf("%d ", n);이 실행됩니다.

7. recurse(1):
   호출이 끝난 뒤 printf("%d ", 1) 실행.

8. recurse(2):
   호출이 끝난 뒤 printf("%d ", 2) 실행.

9. recurse(3):
   호출이 끝난 뒤 printf("%d ", 3) 실행.

10. recurse(4):
    호출이 끝난 뒤 printf("%d ", 4) 실행.

11. recurse(5):
    호출이 끝난 뒤 printf("%d ", 5) 실행.
    최종 출력
    재귀 호출이 끝난 뒤 출력이 순서대로 실행되므로, 최종 출력은:

코드 복사
1 2 3 4 5

간단하게 정리하면 함수호출만 stack 메모리에 저장되다가 함수 호출이 끝나면 역순으로 다시 리턴값을 프린트해준다.