도와주세요

[Python 질문] 재귀함수의 알고리즘이 잘 이해가 되지 않습니다.

맛스타2019.02.09 23:21조회 수 154댓글 13

    • 글자 크기

파이썬공부를 하던 중 재귀 함수에 대해 공부하다 어떤 과정으로 프로세스가 이루어지는지 잘 이해가 되지 않아 질문드립니다.


일단, 특정수가 홀수인지 짝수 인지 확인하는 함수입니다.

조금 더 효율적으로 작성할 수도 있지만 재귀함수를 공부하는 도중에 작성한 코드이기 때문에 다른 형태의 코드에 대해서는 감사하지만 따로 알려주시지 않아도 됩니다.


예를 들어 is_odd(17) 을 확인했을 때 True 를 반환하고 is_odd(18)을 확인할 때는 False 가 나오도록 합니다.

반면, is_even(17)을 입력하면 False를, is_even(18)을 입력하면 True를 반환합니다.


def is_even(x):
    if x==0:
        return True
    else:
        return is_odd(x-1)

def is_odd(x):
    return not is_even(x)



여기에 아래처럼 테스트 해보면 아래와 같은 결과가 나옵니다.


print(is_odd(19))
True

print(is_even(19))
False



Sololearn을 통해 공부하던 중 is_even(19)를 입력했을 때 False 가 나오는 과정을 상세하게 설명을 듣고자 합니다.


제가 이해한 바로는

is_even(19)를 입력하면 19가 0이 아니기 때문에 is_odd(18)을 리턴시키고

is_odd(18)에서는 not is_even(18)을 반환하는 것으로 이해했습니다.


not 구문이 들어가서 어떻게 해석(이해)을 해야하는지 궁금합니다.

신나는 도박사이트!


https://studyforus.com

    • 글자 크기
SQL문을 PHP에서 실행시켰는데 안되네요 (by Piedots) 하천 복개 공사가 서버에 영향을 미칠까요? (by 이니스프리)
  • 2019.2.9 23:48

    is_even(19)을 입력했을 때 19가 0이 아니기 때문에 else 부분에 있는 is_odd(18)이 실행해서 해당 값을 반환합니다.
    그리고 is_odd(18)에서는 is_even(18)을 실행해서 나온 결과에 not 연산자를 적용하게 됩니다.
    is_even(18)은 다시 18이 0이 아니기 때문에 else 부분에 있는 is_odd(17)을 실행해서 해당 값을 반환합니다. 이것을 계속 반복해서 is_even에 0이 호출될 때까지 실행합니다.
     

    어떤 식으로 함수가 호출되는지 알고 싶으시다면 아래와 같이 print 함수를 쓰는 것도 괜찮습니다.


    def is_even(x):
        print('call is_even({})'.format(x))
        if x==0:
            return True
        else:
            return is_odd(x-1)
     
    def is_odd(x):
        print('call is_odd({})'.format(x))
        return not is_even(x)
    
    print(is_even(19))



  • @humit
    맛스타글쓴이
    2019.2.10 03:18

    한번 이대로 실행해보겠습니다. 감사합니다!

  • 이건 파이썬 자체의 문제가 아니라 코딩 차원의 문제인 것 같군요 ^-^


    재귀함수는 너무 난해해서 저도 텍스트북이나 수업을 통해서 배우기만 하고 실제로 사용해본 기억은 거의 없네요 ㅠㅠ

    (저처럼 날림으로 파이썬을 공부한 사람의 특징인 것 같습니다 ㅜㅜ)



    우선 not은 boolean 연산자로서 기존값의 반대값을 취합니다.


    True에 대해 False를, False에 대해 True를 취하게 됩니다.


    즉 논리학에서의 '~'와 동일한 의미입니다.


    올려주신 스크립트에서는 is_even(x)값에 not이 붙으면 반대의  boolean 값을 취하게 됩니다.



    19는 숫자가 크니 작은 숫자로 예를 들어 계산과정을 설명드릴게요.


    x가 1씩 감소하면서 0이 될 때까지 not이 몇 번 붙느냐에 따라서 최종 boolean 값이 결정됩니다.


    이건 파이썬이 아니라 논리학의 측면에서 접근하시면 수월합니다 :)


    is_even(3)

    is_odd(2) 

    not is_even(2)

    not is_odd(1)

    not (not is_even(1))

    not(not is_odd(0))

    not(not(not is_even(0)))

    not(not(not True)))

    not(not False)

    not True

    False

    is_even(2)

    is_odd(1)

    not is_even(1)

    not is_odd(0)

    not(not is_even(0))

    not(not True)

    not False

    True



    괄호 때문에 위와 같이 정석적(?)으로 정리하긴 했지만 


    기계가 아닌 사람이 머리 속에서 계산을 할 때에는 not과 not이 만나면 지워진다고 생각하시면 보다 간단합니다 ㅎㅎ


    위에 정리한 것처럼 is_even() 함수에 어떤 정수를 집어넣었을 때 


    최종적으로 False가 도출되면 not이 홀수번 붙고, True가 도출되면 not이 짝수번 붙는다고 생각하시면 되겠네요.



    대략 다음과 같은 방법으로 함수에서 변수를 찍어보시면 이해에 도움이 되실거에요~!


    def is_even(x):
        if x==0:
            return True
        else:
            print('even' + str(x))
            return is_odd(x-1)
     
    def is_odd(x):
        print('odd' + str(x))
        return not is_even(x)



    +) 

    답변을 작성하는 사이에 humit 님께서 이미 저보다 정확한 답변을 달아주셨군요 ^^

    humit 님께서 올려주신 스크립트처럼 else가 아니라 is_even 함수의 첫 단계에서 값을 찍어보는 것이 좋을 것 같네요.


    ++)

    외람된 말씀이지만... 재귀함수를 공부하다보면 프로그래밍 공부가 너무 어려워서 재미없지 않으신지요?? ㄷㄷ

    이 파트가 저만 어렵다고 생각하는 것인지도 모르겠네요 ㅠㅠ



    +++)

    재귀함수와 관련은 없지만 제 허접한 수준에서 그나마 파이썬스러운 스크립트를 작성해보면 다음과 같습니다.


    def even_or_odd(number):
        print("even" if number % 2 == 0 else "odd")



  • @이니스프리
    맛스타글쓴이
    2019.2.10 03:21

    is_even(3)

    is_odd(2)

    not is_even(2)

    not is_odd(1)

    not (not is_even(1))

    not(not is_odd(0))

    not(not(not is_even(0)))

    not(not(not True)))

    not(not False)

    not True

    False

     

     

    is_even(2)

    is_odd(1)

    not is_even(1)

    not is_odd(0)

    not(not is_even(0))

    not(not True)

    not False

    True

     

    이 부분으로 파악했습니다.

    결국엔 not을 붙인채로 is_even 함수를 계속 사용하는 거였군요.

     

    이제 이해되었습니다.

     

    not 인채로 is_even 안의 함수 내용을 살펴보다 보니 어떻게 해석해야 하는 건가 했는데 확실히 이해되었습니다. 감사합니다!!

     

    그리고 재귀함수는 여러가지 상황을 더 자유롭게 할 수 있는 흥미있는 내용인것 같습니다.

    다행이 "타의"에 의해 (취업이나 학과 과정) 공부하는 것이 아닌 "흥미"를 위한 공부여서 그런지 하나하나 배우는게 재밌네요~

  • @맛스타
    2019.2.10 09:54

    오오~ 제가 개떡 같이 설명을 드렸는데 다행히 찰떡 같이 이해하셔서 다행이네요 ^-^

    말씀하신대로 boolean 값에 not이 하나씩 붙으면서 x==0일 때까지 재귀함수가 계속 돈다고 생각하시면 되어요.

    일반적인 정수나 문자열 변수가 아니라 boolean 변수이기 때문에 다소 특이한 경우라고 볼 수 있겠네요.

    저는 재귀함수가 너무 어려워서 응용적인 측면에서는 사실상 포기를 했는데 이 파트가 재미있으시다니 다행이네요 :)

    (재귀함수도 어렵고 논리학도 어렵네요 ㅠㅠ)

     

    그리고 말씀드린대로 이해가 안 되는 스크립트에서는 변수값을 찍어보는 것이 이해에 도움이 되더군요.

    이 스크립트 같은 경우에도 대입하는 정수값이 5 이상으로 커지면 인간의 머리로 boolean 값을 계산하는 것이 골치가 아파서요 ㄷㄷ

     

    그럼 감기 조심하시고 즐거운 주말 되세요!

  • @이니스프리
    맛스타글쓴이
    2019.2.10 11:00

    중학교??고등학교?? 수학때 배운 명제 파트가 생각나네요.

     

    p=>q 인 명제와 그 대우인 ~q=>~p 가 서로 성립한다. 했던 그런 내용이요 ㅋㅋ

  • @맛스타
    2019.2.10 12:42

    그러게요~! 제 기억이 맞다면 교과서상으로는 고1에 수록되어 있던 것 같고 많은 학생들이 중2, 3 정도에 공부했던 것 같네요 ㅎㅎ

    아마도 p -> q와 그 대우인 ~q -> ~p는 논리적 동치라는 내용이었죠 ^^

    증명을 어떻게 하는지는 기억이 안 나네요 ㅠㅠ

  • @이니스프리
    맛스타글쓴이
    2019.2.10 14:26

    역 이 대우 중에 대우 명제로 기억하네요. ㅎㅎ

  • @이니스프리
    2019.2.10 19:12

    p->q일때 ~q지만 p인 경우가 있다고 하면 p->q가 거짓이 되죠?

  • @abnoeh
    맛스타글쓴이
    2019.2.10 19:23

    이미 p->q 인 참인 명제에서 ~q -> p 가 될 수 있는 명제가 없습니다.

     

    q의 진리집합이 p의 진리 집합 보다 크고 p집합은 q집합의 부분집합이 되기 때문에 q집합의 여집합은 p집합의 부분집합이 될 수없습니다.

     

    만약 전체 명제를 u라고 하면 p, q , u 집합이 모두 같다면 가능하긴 하겠네요. 그땐 p->q인 명제는 거짓이 될 수 없겠지요.

     

     

  • @맛스타
    2019.2.10 19:29

    그니까 귀류법으로 (p->q)->(~q->~p)가 증명되죠

  • @abnoeh
    맛스타글쓴이
    2019.2.10 20:06

    아아 대우 명제의 증명을 이야기하신거군요.

  • 2019.2.10 23:14

    으앗 어려웡

댓글 달기

번호 제목 글쓴이 날짜 조회 수
공지 회원 전용 페이지가 생겼습니다.15 마스터 2018.03.20 5254
공지 [필독] 질문하는 방법5 마스터 2018.02.23 717
539 그누보드 5 설치 오류 도와주세요3 김호창 2019.02.15 81
538 TXT레코드 관련 도와주세[요!7 AA 2019.02.14 89
537 라이믹스 ckeditor42 캣치 2019.02.13 60
536 SQL문을 PHP에서 실행시켰는데 안되네요7 Piedots 2019.02.11 68
[Python 질문] 재귀함수의 알고리즘이 잘 이해가 되지 않습니다.13 맛스타 2019.02.09 154
534 하천 복개 공사가 서버에 영향을 미칠까요?4 이니스프리 2019.02.09 64
533 미국 간편식 추천 부탁드립니다14 이니스프리 2019.01.29 108
532 라엘 님의 이미지 캐시 서버 구축하기와 관련하여 구체적인 방법을 여쭤봅니다4 이니스프리 2019.01.27 104
531 일본어 '도키도키'의 뜻을 어떻게 해석해야 하나요?11 이니스프리 2019.01.26 122
530 아이폰8+ 네비 사용시 발열(?) 문제에 대한 해결책을 여쭤봅니다10 이니스프리 2019.01.26 109
529 파이썬 공부하다 모르는 부분이 있습니다.14 맛스타 2019.01.26 133
528 XE/php 질문 2가지 title: 만렙이 되어보자도토리묵 2019.01.25 46
527 trumbowyg 에디터를 그누보드 아미나빌더에 삽입중입니다.10 홀민 2019.01.25 94
526 PHP 순서 매기기3 title: 에그joyful 2019.01.23 52
525 세션연동부분에 대하여 도움이 필요합니다.2 Hanam09 2019.01.21 51
524 Input submit 버튼2 Piedots 2019.01.20 50
523 x-y넷에서 내 웹사이트에서 트래픽 사용 현황을 볼 수 있는 php소스가 있었습니다2 없음 2019.01.20 58
522 POST 데이터가 보내지지 않습니다5 Piedots 2019.01.20 64
521 도메인 포워딩이 제대로 이루어지지 않습니다.4 title: 애프터 이펙트제르엘 2019.01.20 58
520 게시판 중복확인 만들다가 너무 허탈해서 올려봅니다5 Piedots 2019.01.19 95
이전 1 2 3 4 5 6 7 8 9 10... 27다음
첨부 (0)
서버에 요청 중입니다. 잠시만 기다려 주십시오...