재귀 (Recursion)

재귀

큰 상자 속에 작은 상자들이 있고, 그 작은 상자들 안에는 더 작은 상자들이 있다. 그리고 열쇠 하나가 그 상자들 속 어딘가에 있다고 했을 때, 열쇠를 찾기 위한 알고리즘을 고민해보면 아래와 같은 방법들이 있다.

첫번째 while반복문

내부를 확인할 상자를 쌓아놓는다.
상자를 하나 집어서 내부를 살핀다.
만약 상자가 있다면 꺼내어 나중에 확인할 상자 더미에 놓는다.
만약 열쇠가 있다면 작업이 종료된다.
반복한다.

##의사코드
def look_for_key(main_box) :
    pile  = main_box.make_a_pile_to_look_through()
    while pile is not empty :
        box = pile.grab_a_box()
        for item in box :
            if item.is_a_box() :
                pile.append(item)
            elif item.is_a_key() :
                print "key found!"

두번째 재귀(recursion)

상자 안을 확인한다.
만약 상자를 발견하면 1단계로 간다.
만약 열쇠를 발견하면 작업이 종료된다.

##의사코드
def look_for_key():
    for item in box :
        if item.is_a_box():
            look_for_key(item)  ##반복
        elif item.is_a_key():
            print "key found!"

풀이를 더 명확하게 만들어 준다.
성능이 더 나아지지는 않는다. (반복문이 더 나은 성능을 보일 때가 많다.)
대부분의 중요한 알고리즘들이 재귀를 사용하므로 개념 숙지가 중요하다.
프로그램에 반복문을 사용하면 프로그램의 성능을 향상시킬 수 있지만, 재귀를 사용하면 프로그래머의 능력을 향상시킬 수 있다. 상황에 따라 적절한 방법을 골라 사용하는 것이 좋다.

기본 단계과 재귀 단계

재귀 함수는 자기 자신을 호출하므로 실수로 무한 반복하는 함수를 만들지 않도록 주의할 필요가 있다. (언제 재귀를 멈출지 반드시 알려줘야 한다.)

그래서 모든 재귀함수는 기본단계(base case : 자기 자신을 호출하지 않는 부분. 즉, 무한 반복으로 빠져들지 않게 하는 부분.)와 재귀 단계(recursive case : 자기 자신을 호출하는 부분)라는 두 부분으로 나누어져 있다.

스택 (stack)

호출 스택은 재귀 뿐 아니라 일반적인 프로그래밍에서도 중요한 개념이다.
스택에는 푸시(push : 추가)와 팝(pop : 반환) 이라는 두가지 연산이 있다.
여러개의 함수를 호출하면서 함수에 사용되는 변수를 저장하는 스택을 ‘호출 스택(call stack)‘이라고 한다. 모든 함수 호출은 호출 스택을 사용한다.

##팩토리얼 함수(factorial function)
def fact(x) :
    if x ==1 :
        return 1
    else 
        return x*fact(x-1)


##재귀 호출 스택
"""

코드                 호출 스택       
______________________________________
                
fact(3)             [ fact | x | 3 ]
--------------------------------------
if x == 1:          [ fact | x | 3 ]
--------------------------------------
else:               [ fact | x | 3 ]
--------------------------------------
return x*fact(x-1)  [ fact | x | 2 ]        <----재귀호출
                    [ fact | x | 3 ]
______________________________________

if x==1:            [ fact | x | 2 ]        <----fact함수에 대한 두번째 호출(x값이 2)
                    [ fact | x | 3 ]            가장 위에 있는 함수 호출이 실행인 호출이다.
--------------------------------------
else:               [ fact | x | 2 ]        <----*주의* 두 함수 호출 모두 x라는 이름의 변수를
                    [ fact | x | 3 ]            가지고있지만 x의 값은 다르다.
--------------------------------------
return x*fact(x-1)  [ fact | x | 1 ]
                    [ fact | x | 2 ]
                    [ fact | x | 3 ]
______________________________________

if x==1:            [ fact | x | 1 ]
                    [ fact | x | 2 ]
                    [ fact | x | 3 ]
--------------------------------------
return 1           >>>  [ fact | x | 1 ]     <----스택에서 pop할 첫번째 상자다.(반환 첫번째 값)   
                    [ fact | x | 2 ]             fact함수를 3번 호출했지만 아직 전체 함수 호출을 
                    [ fact | x | 3 ]             마무리 하지 못했다.
______________________________________

return x*fact(x-1) >>>  [ fact | x | 2 ]     <----- 2를 반환한다.
                    [ fact | x | 3 ]
______________________________________

return x*fact(x-1) >>>  [ fact | x | 3 ]     <----- 6을 반환한다.
______________________________________

"""

스택을 사용하면 편리하지만 모든 정보를 저장해야 하므로 메모리를 많이 소비한다. (함수 호출시마다 메모리 사용) 스택이 너무 커졌다는 것은 컴퓨터가 과다한 함수 호출정보를 저장하고 있다는 뜻이다. (스택 메모리가 커지면 stack overflow가 발생할 수 있다.) 이럴경우 선택할 수 있는 방법이 2가지 있다.

재귀 대신 반복문을 써서 코드를 다시 작성 (성능상으로는 for문이 빠르다)
꼬리 재귀(tail recursion)라는 방법을 사용. (고급 재귀방법으로 모든 프로그래밍 언어에서 지원하는 것은 아니다.)

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘

알고리즘 재귀

재귀 (Recursion)

재귀

기본 단계과 재귀 단계

스택 (stack)

reference

SUN