2016년2학기 고급컴퓨터프로그래밍및실습 (36342-02)
LAB #4 : 재귀 함수
1
F(n) : factorial 구하는 재귀 함수
2
factorial 함수 정의
factorial 함수 호출 n Factorial, F(n) 의 정의
F(1) = 1
F(n) = n * F(n-1), n > 1의 경우
F(5) 계산 과정
3
main( )
F(5)
F(5)
5*F(4)
F(4)
4*F(3)
F(3)
3*F(2)
F(2)
2*F(1)
F(1)
1
1 2
6 24
120
(실습1) 합을 구하는 재귀 함수
양의 정수 n 이 입력인자로 주어지면
1 + 2 + 3 + 4 + ... + (n-1) + n 을 구하여 그 값을 리턴(반환)하는 재귀 함수를 작성하시오.
(힌트)
n! = 1 * 2 * 3 * ... * n 으로도 표현될 수 있고,
= n * (n-1)! 로도 표현될 수 있다.
4
위의 합 계산 공식을 이와 같이 수정해 보시오.
(실습1) 빈칸을 채우시오.
5
열어 보세요!
(실습 2) 합 계산 응용
양의 정수 n 이 입력인자로 주어지면, 다음과 같은 작업을 하고, 그 결과를 리턴하는 재귀 함수를 작성하시오.
n 이 짝수인 경우 : 2 + 4 + 6 + ... + (n-2) + n 을 구한다.
n 이 홀수인 경우 : 1 + 3 + 5 + ... + (n-2) + n 을 구한다.
힌트
입력 n이 주어지면 그 값이 홀수인지 짝수인지 점검할 필요 없이 n, n-2, n-4, ... , i 까지 합하면 된다. 단 i >=1.
맨 마지막 step : n + {n-2}까지 합계 계산한 결과
어디까지 내려가야 할까? 1보다 작아지면 안됨
6
(실습 3) 합 계산 응용
입력 인자 2개 (양의 정수 a, n)가 주어진다고 하자. n 보다 작거나 같은 a 의 모든 양의 배수를 더하여 리턴하는 재귀 함수 rsum3( )을 작성하시오.
main( ) 은 다음과 같이 가정하시오. 즉, n 이 a 의 배수가 아닌 경우, main( ) 에서 이를 조정한 후에 rsum3( ) 을 호출한다.
7
힌트: n + (n-a) + (n-2a) + …
(실습 4) 수열 계산 재귀 함수
양의 정수 n이 주어지면 해당 수열의 n번째 수를 리턴하는 재귀 함수를 작성하시오.
함수 f1 : 1, 3, 5, 7, 9, 11, ...
함수 f2 : 2, 4, 6, 8, 10, ...
함수 f3 : 2, 5, 8, 11, 14, 17, ...
함수 f4 :1, 3, 9, 27, 81, ....
각 수열을 recursive 하게 표현해 보시오.
f1의 경우, an = an-1 + 2 , 단 a1 = 1
이를 사용하여 재귀 함수를 만듭니다.
8
힌트
(실습5) 숫자 순서대로 출력하기
다음 프로그램은 10, 9, 8, ... , 3, 2, 1 을 화면에 출력한다. 즉, 1~10사이의 수를 descending order (내림차순)으로 출력한다. Descend( ) 함수를 약간 수정하여, 1~10사이의 수를 ascending order (오름차순)으로 출력하도록 해 보시오.
9
힌트
출력을 먼저 할까, 호출을 먼저 할까?
(복습) Fibonacci number 구하는 재귀함수
10
재귀함수
여러 번 호출하는 경우
11
F(5) 계산 과정
F(5) F(4) + F(3)
F(4) F(3) + F(2)
F(3) F(2) + F(1)
F(2) F(1) + F(0)
F(1) 1 F(0) F(1) 0
1
F(3) F(2) + F(1)
F(2) F(1) + F(0)
F(1) 1 F(0)
0 F(1)
1 F(2)
F(1) + F(0)
F(1) 1 F(0)
0
재귀함수 작성할 때 기억할 것은~
12
n 이 줄어들다가 0이나 1이 되면 더 이상의 호출을 끝내야 한다.
그 상황에 대한 처리가 있어야 한다.
Fib(n)을 구하기 위한 맨 마지막
단계에 대한 정의가 여기에 있어야 한다.
(실습6) Tower of Hanoi
13
Tower of Hanoi (1/2)
http://www.mathsisfun.com/games/towerofhanoi.html
14
phase 1
a
na
n-11
Tower of Hanoi (2/2)
15
a
n-1a
nphase 2
(실습6) Tower of Hanoi
원반이 n 개 일 때, 원판 몇 개 옮겨야 하는가를 계산하는 int hanoi(int n) 을 정의하고, 제대로 작동하는지 테스트해 보시오.
16
