[알고리즘/Algorithm] 파이썬으로 재귀함수 알아보기

재귀함수란

함수 안에서 자기 자신(함수)을 다시 호출하는 함수를 말한다.

 

함수 안에서 함수를 쓴다는 것이 처음에는 잘 와닿지 않았고 딱히 왜 써야 하는지도

모르겠고 이해가 쉽지 않았다. 

 

그래서 공부를 살짝 해봤고 그것을 쉽게 풀어쓰기 위해서 코드를 가지고 왔다.

def recrusive(data):
    if data < 0:
        print("ended")
    else:
        print(data)
        recrusive(data-1)
        print("returned", data)

위에 파이썬 코드를 보면 recrusive 함수 선언문 안에서 recrusive 함수를 호출하고 있다.

이것이 함수 안에서 함수를 다시 호출하는 것을 말하는데..

 

코드만 보면 이 코드가 어떻게 동작할까를 이해하는 것이 처음보는 사람한테는 쉽지가 않다..

 

우선 이 함수에 동작을 보자면 이런식이다.

recrusive(4)

'''
결과 : 
4
3
2
1
0
ended     
returned 0
returned 1
returned 2
returned 3
returned 4
'''

왜 이렇게 나올까?

 

우선 이 코드의 결과를 이해하기 전에 재귀함수가 어떻게 작동하는지 살펴볼 필요가 있다.

 

재귀함수는 함수 안에서 함수를 호출하고 또 그 함수 안에서 함수를 호출하기 때문에 어떤 상황에 도달하면 함수를 탈출하는 조건이 있지 않으면 무한히 반복돼서 스택오버플로우 에러를 유발한다.

 

그렇기 때문에 함수를 탈출하는 조건이 무조건 있어야 하고 그 조건이 위에 코드 상에서는 

 if data < 0:
        print("ended")

이 구문이 된다.

 

결과적으로 함수 실행 중 이 조건에 일치하여 이 구문에 도달하게 되면 'ended'를 print하고 함수가 종료되게 된다.

 

하지만 결과를 보면 'ended'를 print하고도 'return 0' ~ 'return 4'까지가 출력 되는데 그 이유는 함수가 스택에 쌓여있다가 

차례대로 실행되기 때문이다.

 

함수가 스택에 쌓이는 것을 이해하는 것은 그림으로 보면 빠르다.

이런 식으로 실행된다.

1. recrusive(4)가 스택에 쌓이고 동작한다.
2. 1이 동작하면서 print 4가 되고 다시 recrusive(n-1)을 호출한다.
3. recrusive(3)이 스택에 쌓이고 동작한다.
4. 3이 동작하면서 print 3이 되고 다시 recrusive(n-1)을 호출한다.
5. 종료 조건까지 반복...

 

이런식으로 종료 조건까지 반복하다 보면 이런 그림이 완성된다.

이 다음엔 그러면 recrusive(-1)이 호출 될 것이고 그러면 if문 조건에 걸리게 되어

추가로 'ended'를 print 해주고 함수가 더이상 호출되지 않을 것이다.

 

그러면 최종적으로 스택에 쌓였던 함수가 위에서 부터 빠져나오면서 동작할 것인데.

 

recrusive(0)부터 recrusive(4)까지 스택에서 빠져나오면서 

print("returned", data)

이 구문이 실행될 것이다.

 

여기서 좀 헷갈릴 수 있는게 왜 그동안 'returned n'이 출력이 안 되고 한번에 출력 되냐면 

 else:
     print(data)
     recrusive(data-1)
     print("returned", data)

이 else 구문에서 recrusive(n)이 재귀 호출로 다시 호출 되었기 때문에 밑에 줄 코드에 접근을 하지 못했기 때문이다.