[C언어] # 9. 재귀함수 (Recursive Function)

Crush_on_Study·2022년 6월 10일
0

C언어 기초

목록 보기
10/11

오늘 다룰 내용은 재귀함수입니다. 혹시 요즘도 고등학교 수학에서 수열을 배울 때, 재귀도 같이 배우는지 모르겠네요.

필자는 현재 28살이라 수능본지가 까마득해서 ㅎㅎ

재귀함수!

재귀라는 것은 '자기 자신을 호출하는 개념'이다!

  • 이게 무슨 말인가요?

말 그대로, 함수가 종료될 때 return 값을 자기 자신으로 한다는 것입니다.
일반적으로 우리가 작성하는 코드는

#include <stdio.h>
int main()
{
	 int n=2022;
     printf("%d",n);
     
     return 0;
}

이런 식으로 'main'이라는 이름을 가진 함수가 정상적으로 종료될 때 0값을 반환해라! 라는 식으로 짭니다.

그런데 만약, return 값을 main으로 한다면 어떻게 될까요?
시도는 안해봤지만 함수가 종료됨과 동시에 main함수를 다시 호출함으로써
위 코드는 계속해서 2022가 무한하게 출력될 것입니다.

  • 그럼 반복문이랑 똑같은 기능을 하지 않나요?

너무 훌륭한 질문입니다. 맞아요. 반복문이랑 똑같습니다. 그럼 왜 애써 배운 반복문을 냅두고 또 똑같은 기능을 하는 재귀함수를 배워야 하느냐?
재귀함수를 이해하는 것이 탐색알고리즘의 시작이 되기 때문입니다.

Stackoverflow

혹시 코딩을 좀 하신분들은 많이 들어봤을 사이트인데요,
StackOverFlow (스택오버플로우)
이 사이트의 제목은 재귀함수와 연관이 있습니다. 재귀함수라는 것은
겉으로 보기엔 반복이지만, 내부를 좀 파헤쳐보면 '원문'을 복사하여 그것을 팬케이크를 쌓듯이 복사본, 복사본, 복사본, 복사본,..... 을 생성하여 반복을 수행하는 것입니다.


이 사진처럼 어떤 상자에 주황색 바같은게 쌓이다보니 상자 위로 넘쳐나게 됩니다. 재귀함수를 통해 무한한 복사본을 생성하여 반복을 수행하다보면 어느샌가 그 복사본들을 담아놓은 메모리 공간이 부족하게 되서 넘쳐나게 됩니다. 이러한 현상을 '스택 오버플로우' 라고 하며, 이 에러가 발생하면 반복을 멈추고 강제종료가 됩니다.


코드 설명

  • 이제 코드를 보면서 이해해봅시다.
#include <stdio.h>

int repeat (int n)
{
	printf("%d\n",n);
	if (n==0)
	{
		printf("END");
		return 0;
	}
	
	return repeat(n-1);
}


int main()
{
	int n;
	scanf("%d",&n);
	repeat(n);
	
	return 0;
}

결과 화면

자, 우리는 이제 main함수가 아닌 다른 함수와 마주하게 되었습니다. 겁먹을 것은 없습니다.
함수가 실행되는 순서부터 한번 설명드릴게요. C언어에서는 프로그램이 완성되고 이를 돌려보면 가장 먼저 main함수로 갑니다.

재귀함수 실행 절차

ㅇㅋ, main함수를 호출. 그 다음은?

  • 천천히 코드를 읽어내려가죠. 아하, 사용자가 n을 정수형 타입으로 선언했군.
  • 아하, 그리고 이 n을 입력받고자 하는군.
  • 아하 repeat 함수를 호출했군. 매개변수는 위에서 입력받은 n이구나.
  • ok, repeat함수로 가보자. n을 전달받았구나.
  • ok, n을 출력하면 되는구나.
  • if문을 따르면 n이 0일 때만 수행하는 것이니 return repeat(n-1)로 가자.
  • repeat(n-1)을 반복하다보니, n이 0이 되었다. END를 출력하고 프로그램이 정상 종료 되었음을 알리자.

이런 식으로 수행이 됩니다. 어떤 코드든지 간에, main함수부터 시작하는 것은 국룰입니다.

이런 식으로요. 여러분들이 제 위에 코드 복붙해서 Visualize Code에 들어가셔서 수행해보시면 코드가 수행되는 절차를 눈으로 확인하실 수 있을 겁니다.

  • 아마 제 코드 복붙하면 5번째 단계에서 Error가 뜰텐데요. 그 이유는 n값이 뭔지 모르기 때문입니다. 여러분들이 int n = 5;로 선언하시고
    돌려보시면 아마 n=0이 될때까지의 수행 절차를 보여줄 것입니다.

핵심은 return값이 함수, 자기 자신이라는 것이죠. Ok! 그럼 여기까지 재귀함수가 갖는 특징을 기초적으로나마 알아보았습니다.
그럼 우리 이제 문제를 같이 풀어보죠.


예제

예제 1. 팩토리얼 결과를 출력해라!

  • 팩토리얼이 뭐에요? : 까먹으셨을 수도 있는데, 팩토리얼은 수학에서 나오는 용어입니다. 예시로, 5! = 5부터 1까지 순차적으로 내려가면서 수열들을 모두 곱한 것을 의미합니다. 그럼 5 4 3 2 1을 다 곱하면 120이 결과로 나오겠죠?

이걸 반복문을 사용하지 않고 재귀함수를 이용해서 구현해보는 것입니다.

Okay! 어렵진 않아요.

일단 main함수부터 구현을 해보자!

#include <stdio.h>
int main()
{
	int n;
    scanf("%d",&n);
    
    return 0;
}

여기까지 짜면 일단 main함수는 끝입니다. 만약 우리가 4!를 구하고자 한다면 변수 n에다가 4를 입력하면 되는 것이니까요.
그럼 팩토리얼을 구현하기 위해서는 4를 1까지로 떨구는 재귀함수를 만들어야 합니다. (사실상 위에서 이미 해답코드를 제시한거나 다름없긴 하죠?)

#include <stdio.h>

int factorial(int n)
{
	??
    
	factorial(n-1);
}

int main()
{
	int n;
    scanf("%d",&n);
    factorial(n);
    
    return 0;
}

여기까지 구현을 해봤습니다. 이제 여러분 몫이에요. ??에 들어갈 코드를 한번 직접 짜보는 걸로 합시다.


추가 예제 : 피보나치 수열

못풀어도 좋습니다. 언제나 말하는 것이지만, 지금은 오히려 한번에 못 푸는게 더 정상입니다! 최대한 고민한 후, 구글링을 합시다.

profile
방구석백수 코드몽키

0개의 댓글