[정보처리기사] C언어 - 중복재귀함수

재귀함수는 아래 링크에서 학습 가능합니다.

 

https://accompani-i.tistory.com/222

 

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

 

 

 

 

중복 재귀함수는 자신을 두 번 호출하는 함수로

단계별로 상수가 나올 때까지 수행하면 된다

 

예제로 알아보면

 

---

 

ex1

 

#include<stdio.h>

int recur(int a, int b) {

if(a<=1)

return a*b

else

return a * recur(a-1, b+1) + recur(a-1,  b);

} 

 

void main() {

int a = 3, b = 2

printf("%d₩n", recur(a,b));

}

 

 

 

 

해설

 

 

	a	b
초기값	3	2

 

1단계 recur(3,2)

a,b값	a	b
	3	2
a<=1 거짓 -> else	3 * recur(2,3) + recur(2,2)

 

이제 recur(2,3) (2단계)과 recur(2,2) (3단계) 를 단계적으로 구해주면 된다.

 

2-1단계 recur(2,3)

a,b값	a	b
	2	3
a<=1 거짓 -> else	2 * recur(1,4) + recur(1,3)

 

2-2단계 recur(1,4)

a,b값	a	b
	1	4
a<=1 참 -> return a*b	1*4 = 4

 

2-3단계 recur(1,3)

a,b값	a	b
	1	3
a<=1 참 -> return a*b	1*3 = 3

 

2-1단계 결과값

recur(2,3) = 2 * recur(1,4) + recur(1,3) = 2*4+3 = 11

 

 

 

3-1단계 recur(2,2)

 

a,b값	a	b
	2	2
a<=1 거짓 -> else	2 * recur(1,3) + recur(1,2)

 

3-2단계 recur(1,3)

a,b값	a	b
	1	3
a<=1 참 -> return a*b	1*3

 

3-2단계 recur(1,2)

a,b값	a	b
	1	2
a<=1 참 -> return a*b	1*2

 

3-1단계 결과값

recur(2,2) = 2 * recur(1,3) + recur(1,2) = 2*3+2 = 8

 

 

1단계 최종값(= 3* 2-1단계 결과값 + 3-1단계 결과값)

3 * recur(2,3) + recur(2,2) = 3*11+8 = 41

 

 

 

---

 

ex2

 

 

#include<stdio.h>

int sub(int n) { 

if(n==0) return 0;

if(n==1) return 1;

return (sub(n-1) + sub(n-2));

}

 

void main() {

int a = 0;

a = sub(4)

printf("%d", a);

}

 

 

 

 

해설

 

a에 4 들고 sub함수 들어가자

 

 

1단계

	sub(n-1) + sub(n-2)
sub = 4	sub(3) + sub(2)

sub(3)을 2단계 sub(2)를 3단계로 다시 가자

 

 

2-1단계

sub(3)

	sub(n-1) + sub(n-2)
sub = 3	sub(2) + sub(1)
결과값	1+1

2-2단계

sub(2)

	sub(n-1) + sub(n-2)
sub = 2	sub(1) + sub(0)
결과값	1+0

if(n==0) return 0;

if(n==1) return 1;

이므로

 

2-2단계 결과값은 1+0인 1
2-1단계 결과값은 1+1인 2

 

 

3-1단계

sub(2)

	sub(n-1) + sub(n-2)
sub = 2	sub(1) + sub(0)
결과값	1+0

 

3-1단계 결과값은 1+0인 1

 

최종값 = sub(3) + sub(2) = 2-1단계 + 3-1단계 = 1+2 = 3

 

답: 3

 

 

 

 

---

 

 

ex3

main()함수를 실행할 때 fib()함수가 호출되는 횟수는???

 

 

#include<stdio.h>

int fib(int n) {

if(n==0) return 0;

if(n==1) return 1;

return (fib(n-1) + fib(n-2));

}

 

void main() {

fib(5)

}

 

 

 

해설

 

5들고 fib함수 들어가자

 

1단계(fib(5))

	fib(n-1) + fib(n-2)
fib(5)	fib(4) + fib(3)

fib(4)는 2단계 fib(5)는 3단계로 호출하자

 

 

 

2-1단계(fib(4))

	fib(n-1) + fib(n-2)
fib(4)	fib(3) + fib(2)

fib(3)은 2-2단계 fib(2)는 2-3단계로 호출하자.

 

2-2단계 fib(3)

	fib(n-1) + fib(n-2)
fib(3)	fib(2) + fib(1)

 

fib(2)는 2-3단계, fib(1)은 1로 return

 

 

2-3단계 fib(2)

	fib(n-1) + fib(n-2)
fib(2)	fib(1) + fib(0)
	1+0

 

fib(2) = 1+0 = 1

fib(3) = 1+1 = 2

fib(4) = 2+1 = 3

 

 

3-1단계 fib(3)

위에서 구했던 fib(3), fib(2)가 있으므로 쉽게 구할 수 있지만, 단계를 살펴보기 위해 다시 적어보면

	fib(n-1) + fib(n-2)
fib(3)	fib(2) + fib(1)

fib(2)는 3-2단계, fib(1)은 1로 return

 

 

3-2단계 fib(2)

	fib(n-1) + fib(n-2)
fib(2)	fib(1) + fib(0)
	1+0

fib(2) = 1+0 = 1

fib(3) = 1+1 = 2

 

 

 

1단계 최종값 = fib(4) + fib(3) = 3+2 = 5

 

 

문제에서 호출되는 횟수를 구하라고 했으니,

1단계에서 fib(5)

2-1단계에서 fib(4),

2-2단계에서 fib(3)+fib(2) / fib(2)+fib(1)/fib(1)+fib(0)

2-3단계에서 fib(1)+fib(0)

3-1단계에서 fib(3)

3-2단계에서 fib(2)+fib(1)/fib(1)+fib(0)

 

총 15회 호출된다.

 

답 15회