Tail-recursive Function, High-order Function

Presentation on theme: "Tail-recursive Function, High-order Function"— Presentation transcript:

1 Tail-recursive Function, High-order Function
전자계산입문 2009/04/03

2 Tail-recursive Function
[문제1] factorial 을 계산하는 함수 fact 를 recursive function 으로 작성한다. [실행결과]

3 Tail-recursive Function
[모범답안] let rec fact n = if n = 0 then 1 else n * fact (n - 1) ;;

4 Tail-recursive Function
[실습] factorial 을 계산하는 함수 fact 를 tail-recursive function 으로 작성한다. [모범답안] let fact n = let rec fact' n accum = if n = 0 then accum else fact' (n - 1) (n * accum) in fact' n 1 ;;

5 Tail-recursive Function
[문제2] exponentiation 을 계산하는 함수 pow 를 recursive function 으로 작성한다. (인자 a와 b를 받아 ab를 계산하는 함수 pow 작성) [실행결과] Pow 3 20(=320)과 같이 pow 함수를 적용하는 경우 Ocaml이 표현 할 수 있는 정수의 범위를 벗어나 overflow 가 발생한다.

6 Tail-recursive Function
[모범답안] let rec pow a b = if b = 0 then 1 else a * pow a (b - 1) ;;

7 Tail-recursive Function
[실습] exponentiation 을 계산하는 함수 pow 를 tail-recursive function 으로 작성한다. [모범답안] let pow a b = let rec pow' a b s = if b = 0 then s else pow' a (b-1) (s*a) in pow' a b 1 ;;

8 Tail-recursive Function
[문제3] 2진수를 10진수로 바꾸는 함수bin2dec 을 recursive function 으로 작성한다. [실행결과]

9 Tail-recursive Function
[모범답안] let rec bin2dec x = if x = 0 then 0 else if x = 1 then 1 else 2 * bin2dec (x/10) + x mod 10 ;;

10 Tail-recursive Function
[실습] 2진수를 10진수로 바꾸는 함수bin2dec 을 tail-recursive function 으로 작성한다. [실행결과]

11 Tail-recursive Function
[오답] 착각하기 쉬운 답 (하지만 반대로 계산 됨 -.-) let bin2dec n = let rec bin2dec' n accum = if n = 0 then accum else bin2dec' (n / 10) (accum * 2 + n mod 10) in bin2dec' n 0 ;;

12 Tail-recursive Function
[모범답안] 또 하나의 변수를 이용해야 함 let bin2dec n = let rec bin2dec' n m accum = if n = 0 then accum else bin2dec' (n / 10) (m * 2) (accum + m * (n mod 10)) in bin2dec' n 1 0 ;;

13 High-order Function 정수 x 와 y 의 합 let sum x y = x + y;; 1. sum 은 무엇인가?
- sum 은 함수이다. type은 int -> int -> int 2. sum 2 3 은 무엇인가? - integer 이며, 그 값은 5 이다 3. sum 2 는 무엇인가? 오류인가? # sum 2;; - : int -> int = <fun> - 오류가 아니다. sum 2는 함수이다.

14 High-order Function 정수 x 와 y 의 합 4. 테스트 # f 10;; - : int = 12 # f 15;;
즉, sum 2는 2를 더하는 함수라 할 수 있다.

15 High-order Function 함수의 argument를 전부 주지 않는 경우 let sum x y = x + y;;
let add2 = sum 2;; add2 5;; 나머지 argument 를 받아 계산하는 함수가 됨 (아래와 완전히 동일한 의미) let add2 x = 2 + x;;

16 High-order Function [실습] string_adder s 는 어떤 문자열 앞에 s를 삽입하여 반환하는 함수 작성
[실행결과] # string_adder;; - : string -> string -> string = <fun> # let hello_adder = string_adder "Hello ";; val hello_adder : string -> string = <fun> # hello_adder "della";; - : string = "Hello della" # let bye_adder = string_adder "Bye ";; val bye_adder : string -> string = <fun> # bye_adder "della";; - : string = "Bye della"

17 High-order Function [모범답안]두 가지 방법
let string_adder s = fun x -> s ^ x;; let string_adder s = let h s x = s ^ x in h s ;;

18 High-order Function [실습] integral f a b 는 int -> int 타입을 가지는 함수 f 를 구간 [a,b]에서 구분구적한 값을 반환하는 함수 작성. 구분구적에 사용하는 수식 [실행결과] # integral;; - : (int -> int) -> int -> int -> int = <fun> # let f x = 3*x*x + x - 9;; val f : int -> int = <fun> # integral f 0 0;; - : int = 0 # integral f 0 10;; - : int = 810

19 High-order Function [모범답안] let integral f a b =
let rec integral' f a b s = if a = b then s else integral' f (a+1) b (f a + s) in integral' f a b 0 ;;