재귀함수란 ?

재귀함수란 ?

• 함수내에서 다시 함수(본인)를 호출하여 사용하는 함수
• 사용시 메모리 스텍이 계속 쌓이면서 탈출 루프를 마련하지 않으면 스텍이 넘치면서 오류 발생
• 반복적인 동작을 수행할 때 주로 사용 되며 for,while 과 같이 반복문으로 대체가 가능
• 재귀할때에는 식을 쭉 작성해 놓고 재귀함수가 끝나는 지점에서 작성한 식을 아래에서 위쪽 방향으로 연산

 

 

예시

def sum(n):
    if n == 0:
        return 0
    return n + sum(n-1) 

sum(4)

 

사진 출처 : https://wayhome25.github.io/cs/2017/04/15/cs-16-1-recursion/

강의노트 15-1. 재귀함수(피보나치, 하노이의 탑, 최소공배수 등) · 초보몽키의 개발공부로그

위의 코드 구문을 보면

n의 수가 0일경우에 해당 함수를 빠져나오도록 만들고 반환 값을 0으로 만들어 두었음

그 뒤 n의 수가 0보다 클 경우 n + 함수를 재호출 하면서 함수의 인자값 -1을 하는 것을 볼수 있음

따라서

n(4) + 함수재호출

함수 인자(4) - 1 = (3) ,

함수 인자(3) - 1 = (2),

함수 인자(2) - 1 = (1),

함수 인자(1) - 1 = (0 : 해당 함수 탈출 )

다음과 같이 식이 만들어 지며 함수 인자 n의 값 1과 - 1 의 결과가 0이 되어

해당 함수를 빠져나오는 구문으로 들어갈때 반환값으로 0이 반환이 되면서 결과는 다음과 같다

최종 반환값 = 함수를 탈출하는 반환값 (0) + 재호출한 함수의 연산식의 역방향 연산 

반환값 (0) + 함수 인자(1) + 함수 인자(2) + 함수 인자(3) + 함수 인자(4) = 10