ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 내 맘대로 프로그램 설계 5. - 리스트와 재귀.
    프로그래밍/설계 2018. 6. 10. 02:17

    내 맘대로 하는 프로그램 설계 시리즈.

    Chapter1 - 간단한 데이터 처리(4섹션)

    2017/12/27 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 1. - 이유와 준비.

    2018/01/11 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 2. - 데이터 타입.

    2018/01/16 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 3. - 함수와 변수.

    2018/05/29 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 4. - 고정 크기 데이터.

    2017/06/30 - [프로그래밍/설계] - 프로그래밍과 추상화에 대하여.[부록]


    Chapter2 - 임의의 데이터 처리

    2018/06/10 - [프로그래밍/설계] - 내 맘대로 프로그램 설계 5. - 리스트와 재귀(현재).



    1. 시작하기.

    시작하기는 지난 시간을 복습하거나, 이번 섹션 내용과 이어지는 것을 체크해주는 역할을 하고 있습니다.


    지금 1~5를 전반적으로 다듬는 중.


    2. 리스트.

    구조체를 사용하면 갯수가 정해져 있는 복합적인 데이터들을 정리하는데 유용하다.

    ex) 색, 음악, 좌표 값


    그러나 길다란 메모 목록처럼 정해진 갯수의 데이터가 아니라면?


    바로 '리스트' 라는게 적격이다.


    2.1 리스트 생성 및 기초 사용법.

    리스트는 비어있는 것부터 시작합니다.

    Code 5.1 - 1

    '()


    응? 어디서 보던 거죠?

    바로 Section 2 - 데이터 타입 의 마지막에 등장했던 널 값(Null)입니다.


    데이터가 없다는 것을 뜻하는 널 값이 곧 비어있는 리스트였다는 뜻입니다.


    기억이 맞나 다시 한번 확인해보죠.

    Code 5.1 -2

    null

    결과: '()


    기존에 배웠던 숫자, 불린처럼 '()도 리터럴 상수입니다.(이하 '()로 표시)

    이젠 리스트에 데이터를 만드는 방법을 알아볼 차례입니다.


    - 리스트 생성법

    (cons 인자 리스트-인자)

    첫번째에 인자 값으로 우리가 원하는 데이터를 넣고, 두번째에는 리스트로 된 인자 값을 넣으면 됩니다.


    실제로 데이터를 넣어볼 차례인데, 작성하다 배가 고프니 음식 데이터를 넣어보겠습니다.



    Code 5.2

    (cons 'pizza '()                       )
    (cons 'ramen
          (cons 'chicken (cons 'pizza '())))

    첫번째는 'pizza라는 데이터만 넣은 것이고, 두번째는 'ramen을 넣고 리스트를 생성 시키는 식으로 'chicken, 'pizza를 넣은 것이죠.

    구조체와 상당히 유사합니다.


    그럼 위의 것은 food-list1, 아랫것은 food-list2로 하고, 원하는 음식의 값이 들어있는지 판단하는 프로그램을 만들어보겠습니다.


    리스트 안에 있는 값을 선택하는 방법을 알아봅시다.


    - 리스트 선택법

    (car 인자 리스트-인자)
    (cdr 인자 리스트-인자)

    결과: 인자, 리스트-인자


    cons로 만들어진 리스트에서 인자를 선택하려면 car를 리스트-인자 부분을 선택하려면 cdr을 쓰면 됩니다.


    잠시 확인해봅시다.

    Code 5.3

    ;;----------constant
    (define food-list1 (cons 'pizza '()                ))
    (define food-list2 (cons 'ramen
                             (cons 'chicken food-list1)))
    
    ;----------list test
    (check-expect (car food-list1) 'pizza)
    (check-expect (cdr food-list1) '()   )
    
    (check-expect (car food-list2)
                  'ramen                    )
    (check-expect (cdr food-list2)
                  (cons 'chicken food-list1))
    (check-expect (car (cdr food-list2))
                  'chicken             )
    (check-expect (cdr (cdr food-list2))
                  food-list1           )

    결과: 모든 6개 테스트 통과함!


    리스트 목록은 나중에도 리스트를 쓰기 위해 상수로 만들어 두었습니다.

    리스트에서 값 추출법까지 알았으니 두 리스트에서 음식이 존재하는지 본격적으로 찾아보도록 하죠.


    +.

    HtDP에서는 null, car, cdr이 empty, first, rest라고 표현되어 있습니다.


    이는 BSL의 특성으로, 학생들에게 더 직관적으로 가르치기 위함입니다.

    원래 Racket에서는 null, car, cdr을 사용합니다.


    저희는 범용성이 있도록 Racket의 방식을 사용합니다.


    2.2 리스트와 재귀.

    문제의 조건을 정리하면 다음과 같습니다.

    $$search-food = \begin{cases}
    \emptyset \ni food-list, & false \\ \\
    (cons \ni food-list) \land (\exists \; a-food \in food-list), & true \\
    (cons \not\ni food-list) \lor (\forall \; a-food \notin food-list), & false
    \end{cases}$$

    1. food-list가 null에 속할 경우 false다.

    2. food-list가 cons에 속하고, food-list에 a-food가 존재할 경우 true다.

    3. food-list가 cons에 속하지 않거나. food-list에 임의의 a-food가 없을 경우 false다.


    Code 5.4 -계약, 목적, 헤더

    ;;search-food : food food-list -> boolean
    ;;Contain food in food-list?
    (define (search-food  a-food food-list))

    여러분도 익숙해졌을 계약, 목적, 헤더를 기술 해놓았습니다.


    천천히 함수 템플릿을 만들어 갑시다.

    (define (search-food  a-food food-list)
      (cond
        [(null? food-list) #false]
        [(cons? food-list) ......]))

    가장 먼저 해야할 것은 food-list가 빈 리스트인지, 리스트는 맞는지 확인해야 합니다.

    a-food를 찾는 건 나중의 일이죠.


    문제 조건대로(수식 정리 참고.)
    리스트인 food-list에 있는지 확인해야 합니다.

    (define (search-food  a-food food-list)
      (cond
        [(null? food-list) #false]
        [(cons? food-list)
         ... (equal? a-food (car food-list)) ... (cdr food-list) ... ]))

    a-food가 food-list의 인자 값이 같은지 체크하고, 아니라면 리스트-인자 값과 비교해보아야 합니다.

    (define (search-food  a-food food-list)
      (cond
        [(null? food-list) #false]
        [(cons? food-list)
         (cond
           [(equal? a-food (car food-list)) #true]
           [ else   ...    (cdr food-list)  .....])]))

    food-list에서 리스트-인자를 추출해내고, 추출된 food-list로부터 다시 a-food가 있는지 찾아야 합니다.


    food-list에서 a-food가 있는 것을 찾는 것이 어떤 것이었죠?

    지금 우리가 작성 중인 함수인 'search-food' 입니다.

    Code 5.4 - 최종

    (define (search-food  a-food food-list)
      (cond
        [(null? food-list) #false]
        [(cons? food-list)
         (cond
           [(equal? a-food (car food-list))      #true]
           [ else (search-food a-food (cdr food-list))])]))
    
    (check-expect (search-food 'pizza food-list1  ) #true )
    (check-expect (search-food 'chicken food-list1) #false)
    (check-expect (search-food 'cake food-list1   ) #false)
    
    (check-expect (search-food 'pizza food-list2  ) #true )
    (check-expect (search-food 'chicken food-list2) #true )
    (check-expect (search-food 'cake food-list2   ) #false)

    결과: 모든 6개 테스트 통과함!


    search-food란 함수 내용을 보면 search-food가 자신(search-food)를 참고하고 있죠.

    자기 자신을 참조하는 함수를 재귀(再歸, recursion)함수라고 합니다.


    재귀함수는 직관적이기 때문에 프로그램 작성을 편하게 만들어 주며, 알고리즘 문제 해결에서 기초적인 역할을 해줍니다.

    (처음 배우는 거라 아직 익숙치 않아 어렵다고 느낄 수도 있지만 재귀를 사용하면 쉬워지는 문제들이 꽤 있습니다.)

    이해가 잘 되지 않는다면 '한 단계씩 실행'기능을 꼭 사용해보세요.


    재귀함수를 만들 때 조심해야 할 것은 '탈출조건'을 1개 이상 작성해야 한다는 것입니다.

    search-food에서는 null? food-list나 equal? a-food (car food-list)부분이 탈출조건 이었죠.

    계속 재귀만 한다면 프로그램이 끝나지 않고, 오류가 생기기는 것은 당연한 일.


    한번 프로그램을 터트려보겠습니다.

    (define (recursion-error args)
      (recursion-error (cons args args)))
    
    (recursion-error food-list2)

    보다시피 재귀가 될 때마다 2배씩 늘려나가는 코드입니다.

    실행을 시키면



    라 팝업 창이 뜬 뒤 Interactions disabled가 출력됩니다.[중지 되었다는 뜻]

    계속 food-list2를 늘려가다 보면 프로그램에 할당된 메모리(램, RAM)이 메모리가 다 차기 때문입니다.


    괴델의 불완전성 원리에 따르면 무모순적인 공리계는 참인 일부 명제를 증명할 수 없으며,
    스스로의 모순성을 증명할 수 없다고들 하죠.


    recursion-error 함수도 똑같습니다.

    재귀가 될 때마다 입력 값을 2배로 늘리는 논리 자체는 문제가 없지만(무모순적임, 흔히 말하는 문법적인 에러가 없음)

    그 체계 밖(Dr.Racket)입장에서는 메모리만 계속 먹을 수 밖에 없는 불완전하고 모순적인 존재입니다.


    메모리(RAM, Random Access Memory).


    프로그램이 실행되는 동안 필요한 정보를 저장하는 곳 입니다.

    RAM이란 저장된 데이터를 순차적이 아닌 임의의 순서(랜덤)에 따라 액세스할 수 있는 데이터 저장소입니다.



    재귀를 이용할만한 문제를 몇가지 풀어보도록 합시다.

    +.

    재귀를 배우기 전까지 리스트와 구조체가 무언가 비슷하다 느끼지 않았나요?


    실제로 구조체를 사용해도 리스트와 비슷하게 구현하는게 가능합니다.

    반대도 똑같고요.


    여기선 구조체를 리스트처럼 사용하는 함수들을 만들어보겠습니다.

    Code 5.5 -1

    ;----------list-like structure
    ;-----constant
    (define-struct st-list (value structs))
    
    ;-----function
    ;;st-cons: value, struct -> struct 
    ;;Like cons.
    (define (st-cons a-value a-struct)
       (make-st-list a-value a-struct))
    
    ;;st-car: struct -> value
    ;;Like car
    (define (st-car a-struct)
      (st-list-value a-struct))
    ;;st-cdr: struct -> struct
    ;;Like cdr
    (define (st-cdr a-struct)
      (st-list-structs a-struct))

    (다만 struct는 이미 정의되어 있어 쓸 수 없으므로 structs로 사용했음.)


    리스트 대신 st-list, cons는 st-cons, car은 st-car, cdr은 st-cdr로 대응되게 만들었습니다.


    작동이 잘 되나 확인하기 위해

    food-list2 내용을 st-food-list라 정의하고 st-search-food를 만들어보겠습니다.

    Code 5.5 - 2

    ;----------food
    (define st-food-list (st-cons 'ramen
                                 (st-cons 'chicken (st-cons 'pizza null))))
    
    ;;st-search-food: food st-food-list -> boolean
    ;;Contain food in st-food-list?
    (define (st-search-food a-food food-struct)
      (cond
        [(null?    food-struct) #false]
        [(st-list? food-struct)
         (cond
           [(equal? a-food (st-car food-struct))           #true]
           [ else   (st-search-food a-food (st-cdr food-struct))])]))
    
    (check-expect (st-search-food 'pizza st-food-list  ) #true )
    (check-expect (st-search-food 'chicken st-food-list) #true )
    (check-expect (st-search-food 'cake st-food-list   ) #false)

    결과: 모든 3개 테스트 통과함.


    정상적으로 작동이 되는 것을 볼 수 있다.

    혹시 다른 언어에서 탐나는 기능이 있다면 이렇게 우회적으로 구현하면 된다.


    2.3 리스트와 재귀의 활용.

    2.3.1 list 함수.

    문제를 풀어보기 전에, cons를 여러번 반복해야만 리스트를 만들 수 있는 것이 걸리지 않았나요?

    Chapter1 부록에서도 명시되어 있듯이 프로그램을 만들 때는 중복을 줄이는 것이 좋습니다.


    다행히 list라는 함수가 알아서 리스트를 만들어주는 역할을 합니다.

    (list 인자1, 인자2, 인자3 ...)

    처럼 쓰면 된다는 의미입니다.


    한번 확인을 해봅시다.

    Code 5.6

    (list 1 2 3 'symbol "string")
    
    (define food-list3 (list 'ramen 'chicken 'pizza))
    
    (check-expect (car  food-list3          )
                                      'ramen)
    (check-expect (cdr  food-list3          )
                  (cons 'chicken food-list1))
    (check-expect (car  (cdr food-list3)    )
                                    'chicken)
    (check-expect (cdr  (cdr food-list3)    )
                                  food-list1)

    결과: (cons 1 (cons 2 (cons 3 (cons 'symbol (cons "string" '()))))), 모든 4개 테스트 통과함!


    list란 함수에 대해 대충 파악이 되었죠?

    모두 리스트를 만들어주고, 가장 안에 있는 리스트는 '() 즉 null로 자동적으로 생성시켜줍니다.


    2.3.2 활용.

    리스트와 재귀를 사용한 문제를 풀어봅시다.

    - 구조체와 함께 새로운 list 생성.

    작성자가 야밤에 배가 고픔에도 계속 작성하다 망상을 하기 시작했다.

    야식 리스트를 생각하기 시작한 것.

    ramen: 2000 won

    chicken: 15000 won

    pizza: 12000 won

    cake: 5000 won

    pork-hock: 17000 won

    jajangmyeon: 6000 won

    jjamppong: 7000 won

    하지만 이 음식들을 다 먹고 계산할 것을 생각하니 골이 땅기기 시작했다.

    구조체로 음식 이름과 가격을 표시한 음식 리스트를 만들고 계산 값을 구하시오.


    음식 구조체와 리스트를 만들어봅시다.

    물론 (define ramen 2000)과 같이 사용하는게 더 알맞지만, 구조체와 함께 사용해보기 위해서.


    Code 5. - 1

    (define-struct food-info (name price))
    
    ;;add-food: food-name, food-price -> food-info
    ;;Create food-info struct.
    (define (add-food a-name a-price)
      (make-food-info a-name a-price))
    
    (define food-list4 (list
                        (add-food 'ramen       2000 )
                        (add-food 'chicken     15000)
                        (add-food 'pizza       12000)
                        (add-food 'cake        5000 )
                        (add-food 'pork-hock   17000)
                        (add-food 'jajangmyeon 6000 )
                        (add-food 'jamppong    7000 )))

    음식 이름과 가격이 들어가는 food-info 구조체와 자동으로 구조체를 생성해주는 add-food 함수를 만들었습니다.

    그리고 food-list4를 방금 전에 배운 list 함수로 만들었습니다.


    food-list4 내용

    (cons
     (make-food-info 'ramen 2000)
     (cons
      (make-food-info 'chicken 15000)
      (cons
       (make-food-info 'pizza 12000)
       (cons
        (make-food-info 'cake 5000)
        (cons
         (make-food-info 'pork-hock 17000)
         (cons (make-food-info 'jajangmyeon 6000) (cons (make-food-info 'jamppong 7000) '())))))))

    우리가 원하는 대로 리스트가 생성되었음을 알 수 있습니다.


    Code 5.7 -2

    ;;calulate-price: food-list -> number
    ;;Sum foods' price.
    (define (calculate-price a-food-list)
      (cond
        [(null? a-food-list)                          0]
        [ else  (+ (food-info-price (car a-food-list))
                   (calculate-price (cdr a-food-list)))]))
    
    (check-expect (calculate-price food-list4) 64000)

    결과: 테스트 통과함!


    우선 재귀에서 가장 중요하다고 했던 제한 조건!!

    리스트가 비었는지 확인하고, 비었다면 0을 반환합니다.


    - 간단한 정렬

    food-list4를 내림차순(비싼 것부터 싼 것 순)으로 정렬해보자.


    처음 리스트를 배울 때는 구조체처럼 포함시키는 개념으로 생각해왔는데, car은 값의 추출 cdr은 연결된 리스트로 이동한다고 생각을 바꾸면 좀 더 쉽습니다.


    이제 BSL이 아닌 BSL(List 축약)을 사용하겠습니다.

    cons가 아닌 list를 기준으로 보여주므로 좀 더 간결한 환경에서 사용할 수 있습니다.


    food-list4 내용 - BSL(List 축약)

    (list
     (make-food-info 'ramen 2000)
     (make-food-info 'chicken 15000)
     (make-food-info 'pizza 12000)
     (make-food-info 'cake 5000)
     (make-food-info 'pork-hock 17000)
     (make-food-info 'jajangmyeon 6000)
     (make-food-info 'jamppong 7000))


    그럼 sort-price 함수를 만들어봅시다.

    $$sort-price = \begin{cases}
    \emptyset, & \emptyset \\
    else, & check \; food-info-price \; \&\&  \;sort-price \; next \; food-list
    \end{cases}$$

    sort-price 계약, 목적, 헤더

    ;;sort-price: unsorted food-list -> sorted food-list
    ;;sort food-list
    (define (sort-price a-food-list) ...)


    이를 수식에 있는 조건식 대로 사용하면

    sort-price 함수 템플릿

    (define (sort-price a-food-list)
      (cond
        [(null? a-food-list) null]
        [ else ... (car a-food-list) (sort-price (cdr a-food-list)) ...]))

    함수 템플릿이 만들어집니다.


    함수 템플릿에서 else 부분을 살펴보면

    • car a-food-list는 현재 food-list에서 food-info를 추출
    • (sort-price (cdr a-food-list))에서는 다음 food-list에서 정렬된(sort-price 목적) food-list를 출력

    이란 것을 알 수 있다.


    이 때 필요한 동작은 추출된 food-info를 sort-price가 된 리스트의 적절한 위치에 삽입하는 것이다.

    Code 5.8 - 1

    (define (sort-price a-food-list)
      (cond
        [(null? a-food-list) null]
        [ else (insert (car a-food-list) (sort-price (cdr a-food-list)))]))


    insert 함수도 똑같이 함수 템플릿을 만들어보면

    insert 함수 템플릿

    ;;insert: number food-list -> new food-list
    ;;make new descending order list
    (define (insert a-food-info a-food-list)
      (cond
        [(null? a-food-list) ...]
        [ else ... (car a-food-list) ... (insert a-food (cdr a-food-list)) ...]))


    $$insert = \begin{cases}
    \emptyset \ni food-list, & \left\{ food-info, \emptyset \ \right\} \\ \\
    food-info >= next-food-info, & \left\{ food-info, food-list \right\} \\
    food-info < next-food-info, & \left\{ next-food-info, insert(food-info, next-food-list) \right\}
    \end{cases} $$


    insert 함수는 리스트가 비었을 경우 food-info와 빈 리스트로 만들고,
    food-info의 가격이 다음 food-info 가격보다 같거나 높다면 그대로 생성하며,

    food-info의 가격이 다음 food-info 가격보다 적다면 가격이 같거나 클 때까지 반복한다.

    Code 5.8 - 2

    ;;insert: number food-list -> new food-list
    ;;make new descending order list
    (define (insert a-food-info a-food-list)
      (cond
        [(null? a-food-list) (cons a-food-info null)]
        [ else  (cond
                  [(>=   (food-info-price a-food-info) (food-info-price    (car a-food-list)))
                   (cons  a-food-info     a-food-list)                                        ]
                  [(<    (food-info-price a-food-info) (food-info-price    (car a-food-list)))
                   (cons (car             a-food-list) (insert a-food-info (cdr a-food-list)))])]))

    결과를 확인해보면 잘 작동한다는 것을 알 수 있습니다.

    Code 5.8 - 3

    (check-expect (insert (car food-list4) (cdr food-list4)) (list
                                                               (add-food 'chicken     15000)
                                                               (add-food 'pizza       12000)
                                                               (add-food 'cake        5000 )
                                                               (add-food 'pork-hock   17000)
                                                               (add-food 'jajangmyeon 6000 )
                                                               (add-food 'jamppong    7000 )
                                                               (add-food 'ramen       2000 )))
    
    (check-expect (sort-price food-list4) (list
                                            (add-food 'pork-hock   17000)
                                            (add-food 'chicken     15000)
                                            (add-food 'pizza       12000)
                                            (add-food 'jamppong    7000 )
                                            (add-food 'jajangmyeon 6000 )
                                            (add-food 'cake        5000 )
                                            (add-food 'ramen       2000 )))

    결과: 모든 2개 테스트 통과함!


    아직 완전히 정리가 안되죠?

    sort-price와 insert는 아래와 같이 나타낼 수 있습니다.

    (sort-price ramen chicken pizza cake pork-hook jajangmyeon jamppong)
    (sort-price chicken pizza cake pork-hook jajangmyeon jamppong)
    (sort-price pizza cake pork-hook jajangmyeon jamppong)
    (sort-price cake pork-hook jajangmyeon jamppong)
    (sort-price pork-hook jajangmyeon jamppong)
    (sort-price jajangmyeon jamppong)
    (sort-price jamppong)
    (sort-price '())
    '(jamppong)
    '(jamppong jajangmyeon)
    '(pork-hock jamppong jajangmyeon)
    '(pork-hock jamppong jajangmyeon cake)
    '(pork-hock pizza jamppong jajangmyeon cake)
    '(pork-hock chicken pizza jamppong jajangmyeon cake)
    '(pork-hock chicken pizza jamppong jajangmyeon cake ramen)

    지금 바로 이해가 안되는 분들은 정렬에 대한 것은 뒤에서 더 자세히 다룰테니 리스트와 재귀에 대한 감만 잡고 가면 좋겠습니다.


    마지막 문제로 재귀에만 온전히 집중할 수 있는 문제를 풀어봅시다.

    - 팩토리얼(!)

    팩토리얼은 다음과 같이 나타낼 수 있다.

    $$factorial = \begin{cases}
    n! = \prod_{k=1}^{n} k = n*(n-1)*(n-2)*…*3*2*1 \\
    0!=1
    \end{cases} $$

    1에서 n까지의 모든 자연수의 곱이며, 0일 때는 1인수.

    Code 5.9

    ;;factorial: N -> N
    ;;n*(n-1)*(n-2)*...*3*2*1
    (define (factorial n)
      (if (< n 2)
          1
          (* n (factorial (- n 1)))))
    
    (check-expect (factorial 5) 120)
    (check-expect (factorial 2) 2  )
    (check-expect (factorial 0) 1  )

    결과: 모든 3개 테스트 통과함!


    2.4 리스트와 재귀 좀 더 알아보기.

    2.4.1 리스트 축약.

    BSL(List 축약), Racket, Lisp에서는 list 함수를 더 생략하여 (list 1 2 ..) 대신 '(1 2 ..)처럼 표시 가능합니다.

    '(1 2 ..)는 (quote (1 2 ..))방식과 같습니다.


    이제 '()가 왜 빈 리스트인지 명확하게 알 수 있죠?

    다만 조심해야 할 것은 list와 '의 방식이 완전히 같지 않다는 것 입니다.

    Code 5.10

    '(1 2 variable 'symbol "string" #true)
    '(1 2 (function "string" #true) 3)

    결과: (list 1 2 'variable (list 'quote 'symbol) "string" #true),
    (list 1 2 (list 'function "string" #true) 3)


    일반적인 데이터 유형이 아닌 [함수 or 변수]나 똑같이 '를 붙여서 나타내는 심볼은 예측과 다르게 나오는 것을 볼 수 있습니다.

    variable에는 '가 자동으로 붙여져서 'variable이 되며, 'symbol은 (quote (symbol))로 해석이 됩니다.

    마지막으로 괄호 사이의 fuction "string" #true도 ()에 '이 붙은 것처럼 처리가 되어 하나의 리스트로 해석합니다.


    +.

    BSL이 아닌 Racket에선 eval이란 함수를 사용하면 list를 풀 수 있습니다.


    아래의 코드를 Racket에서 실행해보면

    (equal? (list 1 2 3) '(1 2 3))
    (eval #'(+ 1 2 (* 2 3)))

    결과: #t, 9

    * #t는 #true와 같습니다. #표시는 '후에 나오는 +가 연산자 라는 것을 명시해줍니다.

    가 나오게 됩니다.


    리스트인 '(+ 1 2 (* 2 3))가 eval 연산 후 (+ 1 2 (* 2 3))이 되어 9로 계산됩니다.

    quote 함수나 '역할의 정반대라는 것을 알 수 있죠.


    이 때문에 데이터가 코드가 되기도 하고, 코드가 데이터가 되기도 합니다.

    (define pizza 10)
    pizza
    'pizza
    (eval #'pizza)

    결과: 10, 'pizza, 10


    종합해보자면 ' 표시가 붙으면 데이터가 되는데 eval을 붙이면 데이터를 코드로 바꿀 수 있다는 뜻입니다.

    여기에서 Racket 같은 Lisp 계열에서는 함수나 데이터가 모두 '리스트(list)'라는 결과를 얻어낼 수 있습니다.

    Lisp에서 가장 흥미로운 점이며 무궁무진한 흑마법을 만들어 낼 수 있습니다.


    2.4.2 재귀와 꼬리 재귀.

    우리가 지금까지 배웠던 재귀는 함수가 종료 조건을 만날 때까지 재귀를 하다 종료 조건 후에는 돌아옵니다.

    예컨대 재귀의 깊이(Depth)는 1-2-3-4-5(종료 조건)-4-3-2-1로 표현 할 수 있습니다.


    재귀의 동작처럼 나중에 들어간 것이 먼저 나오는 구조(LIFO, Last In First Out)를 스택(Stack) 구조라고 합니다.

    메모리에서도 재귀가 깊어질 때마다 생기는 인자, 반환 값들, 반환 시 돌아갈 위치값 들을 메모리의 스택 영역에 쌓아놓습니다.

    그런데 스택의 크기가 너무 커지면 다른 프로그램에 방해를 하기 때문에 보통 크기를 제한하게 되죠.


    스택의 제한된 크기를 초과하는 경우를 오버플로우(Overflow)라는 에러가 생깁니다.

    정해진 크기를 초과해서 생긴 오류라고 생각하면 됩니다.


    그리고 재귀 시 스택 오버플로우를 막기 위해 생긴 기법이 바로 꼬리 재귀(Tail Recursion)입니다.

    꼬리 재귀의 핵심 개념은 반환 시 추가 연산이 필요하지 않게 재귀의 꼬리(최종 리턴이 발생하는 곳)까지 필요한 값들을 전달하는 것 입니다.


    위에서 나왔던 팩토리얼을 꼬리 재귀로 구현해보겠습니다.

    ;;factorial-tail: N accumulator -> N
    ;;n*(n-1)*(n-2)*...*3*2*1
    (define (factorial-tail n acc)
      (if (< n 2)
          acc
          (factorial-tail (- n 1) (* acc n))))

    보다시피 다음 연산에 필요한 모든 값들을 인수 형태로 전해주고 있습니다.


    일반적인 팩토리얼 함수와 5!의 연산 과정을 비교해보면

    ;;Factorial
    ;; Output:
    ;; >(factorial 5)
    ;; > (factorial 4)
    ;; > >(factorial 3)
    ;; > > (factorial 2)
    ;; > > >(factorial 1)
    ;; < < < 1
    ;; < < <1
    ;; < < 2
    ;; < <6
    ;; < 24
    ;; <120
    ;; 120
    
    ;;Factorial-tail
    ;; Output:
    ;; >(factorial-tail 5 1)
    ;; >(factorial-tail 4 5)
    ;; >(factorial-tail 3 20)
    ;; >(factorial-tail 2 60)
    ;; >(factorial-tail 1 120)
    ;; <120
    ;; 120

    조금 더 이해가 잘 됩니다.


    꼬리 재귀에서는 불편하게 (factoial-tail 5 1)이라고 값을 넣는데,

    Racket 자체에서는

    (define (factorial-tail n (acc 1))
    ...)

    처럼 사용하면 acc의 기본 값을 1로 정할 수 있습니다.

    HtDP의 언어들은 기능이 제한되서 안되지만..


    그런데 꼬리 재귀도 어쨌든 재귀라 다시 돌아가는 과정이 필요한데 어떻게 스택 오버플로우를 피하는 것이 가능한가.

    답은 컴파일러 최적화에 있습니다.


    컴파일러는 코드를 기계어로 번역 해주는 역할을 합니다.

    이 과정에서 최적화 역시 수행해주고요.


    꼬리 재귀는 결과도 전달을 하기 때문에 앞의 내용은 더 이상 필요하지 않아 반복문으로 바꾸어 줍니다.

    Racket을 기준으로

    (define (factorial-loop n (acc 1))
      (begin (for ([n (in-range 2 (+ n 1))])
        (set! acc (* acc n)))
             acc))

    과 같이 만들 수 있습니다.[정확히 맞는 건 아니만 비스무레한 형태로 바뀝니다]


    코드를 설명하기 전에 못보던 함수들이 좀 보이죠?

    begin은 안에 든 함수들을 순서대로 실행하고 마지막 값을 반환하는 함수입니다.

    (begin (+ 1 2)
             (+ 5 7)
             (* 4 8))

    결과: 32

    보다시피 마지막으로 실행하는 함수인 (* 4 8)의 값인 32만을 반환합니다.


    for은 순서대로 대입을 해주는 함수입니다.

    (for ([x '(1 2 3)])
        (print x))

    결과: 123

    x에 1, 2, 3을 순서대로 대입해줍니다.


    마찬가지로 in-range는 0, 1, 2, 3같은 것을 자동적으로 생성 시켜주는 역할을 합니다.

    (0 부터 시작)

    set!은 예전에 변수의 값을 바꾸는 함수라 했었고요.


    그래서 정리해보면 factorial-loop는

    for문으로 2, 3, ..., (n-1), n순으로 n에 대입하고 acc에 기존 결과값과 n을 곱해 저장해주는 함수입니다.

    마지막으로 저장되었던 acc값을 반환하고요,

    보다시피 재귀가 필요하지 않고 변수의 상태 변화로 해결합니다.


    기존 변수를 바꾸어 사용하니 메모리가 절약되겠죠.


    C언어였으면 상태 변화가 이루어지는 코드가 좀 더 간단했을 테지만 상태 변화를 최대한 지양하는 Racket이다 보니 절차적인 방식으로 코드를 짜면 복잡해 보입니다. 사실 range를 사용하는게 파이썬에서 주로 사용하는 스타일이라 익숙하지 않을 수도.


    +.

    https://black7375.tumblr.com/post/175291125910/재귀가-아름다운-이유

    는 그냥 써본 말..

    재미로만 ㅋㅋ


    3. 후기

    이번 시간에는 리스트와 재귀에 대하여 알아보았습니다.

    분량은 적어졌지만, 내용을 압축적으로 전달하다 보니 어려워 보일 수도 있겠네요.

    다음 시간에는 자료들을 담는 방법인 자료구조에 대하여 알아보도록 할께요.


    친구가 나보고 가끔씩 TMI(Too Much Infomation)끼가 보인다고 하던데 블로그 글쓰면서 왜 그랬는지 느낄 수 있었다..


    아 참!! 어떻게 생각하면 임의의 데이터 처리는 시간과 자원만 주어진다면 무한에 가까운 데이터를 처리할 수 있다는 뜻인데, 무한에 대해 궁금하면

    2018/07/22 - [수학] - 무한, 집합, 그리고 수에 대해서.

    읽어보길.

    댓글

Designed by black7375.