[정보처리기사] C언어 - 재귀함수 (재귀함수 하나만 쓰는 경우)

 

재귀함수란?

 

 

함수 내에서 자기의 함수를 다시 호출하는 함수를 말한다.

스택 내에 차곡차곡 쌓아두었다가 일괄로 처리를 한다.

 

 

 

재귀함수 1개 나왔을 때 -> 박스에 쌓고 하나씩 빼면서 연산

재귀함수 2개 나왔을 때 - > 단계별로 천천히 진행하면서 연산한다.(다음 피드 참고)

 

 

 

바로 예제로 익혀봅시다.

---

 

 

ex1 -> 프로그램 실행 결과에서 세 번째 줄에서 출력되는 것은???

 

 

#include<stdio.h>

int func(int num) {

if(num ==1)

return 1;

else

return num * func(num-1);

}

 

void main() {

int i;

for(i = 5; i >= 0; i--)

{

if(i % 2== 1)

printf("func(%d) : %d₩n",  i, func(i))

  }

}

 

 

 

 

해설

 

 

main함수에서 for문을 먼저 풀어보면

 

int i;

for(i = 5; i >= 0; i--)

{

if(i % 2== 1)

printf("func(%d) : %d₩n",  i, func(i)) -> i와 func(i)호출

 

 

	i	i%2 ==1	func(i)	printf("func(%d) : %d₩n",  i, func(i))
초기값	5
	5	5%2 = 1 (1 == 1 참) -> i ,func(i) 프린트	120	func(5) : 120
	4	4%2 = 0
	3	3%2 = 1 (1 == 1 참) -> i, func(i)프린트	6	func(3) : 6
	2	2%2 =0
	1	1%2 = 1 (1 == 1 참) -> i, func(i)프린트	1	func(1) : 1 <- 세 번째 줄 프린트 되는 값.

 

 

재귀함수를 풀어보자 ( 쌓아두고 일괄처리하자 화살표방향 잘 보자)

func(5)

num	num == 1		num*func(num-1)
5	거짓	else구문	5*func(4)↓	5*24 = 120
4	거짓	else구문	4*func(3)↓	4*6 = 24↑
3	거짓	else구문	3*func(2)↓	3*2 = 6↑
2	거짓	else구문	2*func(1)↓	2*1 = 2↑
1	1 == 1 참	return 1	1→	func(1) = 1↑

상수가 들어오게 되면 재귀함수는 종료되고, func(1)값이 return 받은 1값이 된다.

 

func(3)

num	num == 1		num*func(num-1)
3	거짓	else구문	3*func(2)↓	3*2 = 6
2	거짓	else구문	2*func(1)↓	2*1 = 2↑
1	1 == 1 참	return 1	1→	func(1) = 1↑

 

 

func(1)

num	num == 1		num*func(num-1)
1	1 == 1 참	return 1	1	func(1) = 1

 

답

func(1) : 1 

 

 

 

 

---

 

ex2

 

#include<stdio.h>

int f(int n) {

if(n >0)

return n % 10 + f(n / 10);

else

return 0;

}

 

void main() {

int result;

result = f(123);

printf("%d₩n", result);

}

 

 

 

해설

 

진행 방향은 화살표를 잘 보자

%는 나머지를 구하는 연산, /는 몫을 구하는 연산(정수/정수 = 정수)

f

n	n>0	n % 10	f(n/10)	n % 10 + f(n / 10)
123	참	3	f(12)↓	3+3 = 6
12	참	2	f(1)↓	2+1 = 3↑
1	참	1	f(0)↓	1+0 = 1↑
0	거짓 return 0		0→	f(0)=0↑

 

더이상 f를 재귀하지 않는 순간이 0일 때 f(0) = 0 리턴

 

 

main

result	f(123)	printf("%d₩n", result)
6	6	6

 

답

6

 

 

---

 

반응형

 

 

ex3 

 

 

#include<stdio.h>

int func(int n) {

if(n%2 == 1)

n=n-1;

if(n==0)

return 0;

return(func(n-2)+n);

}

 

void main() {

int result;

result = func(19);

printf("result=%d₩n", result);

}

 

 

 

해설

 

main함수에서 func(19)로 result 산출하라고 했으니,

19들고 func로 들어가자

 

if(n%2 == 1)

n=n-1;

if(n==0)

return 0;

return(func(n-2)+n); -> n==0이 아닐 때의 return 값

 

func

n	n%2 ==1	n=n-1	n==0	func(n-2)+n
19	19%2=1 (1==1 참)	18	거짓	func(16)+18↓	72+18=90
16	16%2=0 (0==1 거짓)		거짓	func(14)+16↓	56+16 = 72↑
14	14%2=0 (0==1 거짓)		거짓	func(12)+14↓	42+14 = 56↑
12	12%2=0 (0==1 거짓)		거짓	func(10)+12↓	30+12 =42↑
10	10%2=0 (0==1 거짓)		거짓	func(8)+10↓	20+10 =30↑
8	8%2=0 (0==1 거짓)		거짓	func(6)+8↓	12+8 =20↑
6	6%2=0 (0==1 거짓)		거짓	func(4)+6↓	6+6 = 12↑
4	4%2=0 (0==1 거짓)		거짓	func(2)+4↓	2+4 =6↑
2	2%2=0 (0==1 거짓)		거짓	func(0)+2↓	0+2=2↑
0	0%2=(0==1 거짓)		참	return 0→	func(0)= 0↑

 

답

result = 90

 

 

 

---

 

ex4

 

실행 결과로 화면에 출력되는 숫자는?

 

#include<stdio.h>

int my(int i, int j) {

if(i<3) i=j=1;

else {

i = i-1;

j=j-i;

printf("%d, %d", i, j);

return my(i,j);

  }

}

 

void main() {

my(5,14);

return 0;

}

 

 

 

 

해설

 

main함수에서 5,14로 my함수를 호출하므로 5,14들고 my함수로 가보자

 

이 문제는 재귀함수긴 하지만, 함수로 연산을 하는 것이 아니기 때문에, my(i,j)를 들고 if문을 수행하면 된다.

 

i	j	i<3	i=j=1	i=i-1	j=j-i	printf("%d, %d", i, j)
5	14	5<3 거짓		4	10	4,10
4	10	4<3 거짓		3	7	3,7
3	7	3<3 거짓		2	5	2,5
2	11	2<3 참	i =1, j = 1			1,1

 

 

답: 4, 10, 3, 7, 2, 5, 1

 

 

 

---

 

ex5 

 

 

#include<stdio.h>

 int recursion(int n){

if(n<5) return 1;

else if(n%5 ==1)

return n+ recusion(n-1);

else recursion(n-1);

}

 

void main() {

int n = recursion(16);

printf("%d", n);

}

 

 

 

 

해설

 

 

main함수에서 recursion(16)으로 n을 출력하라고 했으니 16들고 recursion 함수로 들어가보자

 

n	n<5	return 1	n%5 ==1	n + recursion(n-1)	recursion(n-1)
16	16<5 거짓		16%5 == 1 참	16 + recursion(15)↓		16+18 = 34
15	15<5 거짓		15%5 == 1 거짓		recursion(14)↓
14	14<5 거짓		14%5 == 1 거짓		recursion(13)↓
13	13<5 거짓		13%5 == 1 거짓		recursion(12)↓
12	12<5 거짓		12%5 == 1 거짓		recursion(11)↓
11	11<5 거짓		11%5 == 1 참	11 + recursion(10)↓		11+7 = 18↑
10	10<5 거짓		10%5 ==1 거짓		recursion(9)↓
9	9<5 거짓		9%5 ==1 거짓		recursion(8)↓
8	8<5 거짓		8%5 ==1 거짓		recursion(7)↓
7	7<5 거짓		7%5 ==1 거짓		recursion(6)↓
6	6<5 거짓		6%5 == 1 참	6 + recursion(5)↓		6+1 = 7↑
5	5<5 거짓		5%5 ==1 거짓		recursion(4)↓
4	4<5 참	1		1→		recursion(5) = 1↑
					여기는 연산이 아니고 호출만 하기 때문에 실제 계산에서 빼주게 됨

 

상수 나왔으면 무조건 멈추고 마지막 함수 호출값에 대입한다.

 

 

답

34