재귀함수란?

재귀의 사전적 의미는 자기 자신을 참조한다라고 나와있다..

DFS 구현이나 피보나치 수열에 사용 되는데 어떤 방식인지 이해가 안간다.

예제를 통해 알아보자.

예제

# 0~10 까지 더하는 재귀함수
def Recursion(n):
    if n > 10:
        return n
    print(n)
    Recursion(n + 1)


Recursion(0)

이 소스를 실행해보면 0~10까지 찍힐것이다.

위 소스는 이해가 잘 된다 그렇다면 아래 소스는 어떨까?

def Recursion(n):
    if n > 10:
        return n
    print(n)
    Recursion(n + 1)
    print(n) #추가

Recursion(0)

그저 print문 추가를 해주었다.
결과는 0~10 그리고 10~0으로 거꾸로 출력이 된다.
이게 어찌된 일인지 알아보자.

재귀함수의 동작 원리

예를 들어 0~2까지 더하는 함수라고 생각해보자

def Recursion(n):
    if n > 2:
        return n
    print(n)
    Recursion(n + 1)
    print(n) #추가

Recursion(0)

재귀함수는 스택에 순서대로 쌓인다.
이 함수를 실행하면 이 그림과 같이 쌓인다.

재귀함수로 빨간 선 안에서만 돌기 때문에 0~2까지가 출력이 된다

n이 3일때 return을 하게 되니깐 스택에 쌓인 순서대로 2~0이 출력된다.