[11일차] python 꼬리 재귀함수

python 꼬리 재귀함수에 대해서 정리한다

꼬리 재귀함수를 알아보기전에 재귀함수를 사용하면 안좋은 점에 대해서 알아본다.

- 재귀함수는 하향식 접근법으로 자기 자신을 계속해서 호출한다음에 차례대로

리턴값을 반환해준다. 그런데 여기서 함수가 완전히 종료되지 않았으므로(리턴값을

반환하지 않았다) 함수가 끝날때까지 호출된 위치를 기억해줘야한다.

이때 계속 되는 함수 호출이 반복되다 보면 메모리상 공간이 추가적으로

필요하게 되기때문에 공간을 잡아둬야 한다.

그러면 주소값을 저장하고 있는 스택이 넘치거나 

프로그램의 속도가 느려질수가 있다.

( 공간 복잡도 )

- 값이 클수록 똑같은 리턴값을 가지고 있는 함수의 호출이 여러번 중복 되면서 상당히

비효율적이게 된다.

하지만 꼬리 재귀함수를 사용하면 이런 문제점들이 해결 가능해진다.

---

※ 꼬리 재귀함수

- 꼬리 재귀함수를 이용하면 재귀함수에서 발생하는 공간 복잡도 문제를 해결할수 있고

루프와 시간 복잡도(계산을 반복하는 횟수)는 같아진다.

시간 복잡도에 따라서 알고리즘의 성능이 나뉘어지기도 한다.

O(1) 상수번. 한번만에 끝나는 경우. 가우스. 1에서 10까지 합 (1+10)*5

O(n) n번안에 끝나는 경우정도면 괜찮은 알고리즘이다.

O(log) 절반안에 끝나기 때문에 상당히 괜찮은 알고리즘이다.

O(n^2) 성능이 저하될수 있기 때문에 안좋다.

알고리즘의 성능은 어떻게 보면 같은 횟수를 얼마나 적은 횟수만에 풀어내느냐가 될수 있다.

아래 코드는 재귀함수, 꼬리 재귀함수, 루프문 순서로 n부터 m까지 숫자의 합을 계산해서 값을 반환해주는 함수이다.

나오는 결과는 똑같지만 안에서 동작하는 방식이 다르다는걸 코드를 따라가보면 알수 있다.