꼬리재귀 (재귀함수 안전하게쓰기)

재귀 함수란

https://fast-it.tistory.com/28

재귀함수 (Factorial)

꼬리 재귀?

꼬리 재귀는 재귀 함수의 단점을 보완하기 위해 사용합니다.

일반적인 재귀 함수를 보겠습니다.

보면 자기가 자기 자신을 호출하고 또 호출하고 또 호출하면서 

리턴 값을  받고 받고 받아서  결국 맨 꼭대기(n)에 넘겨주는 겁니다.

 

문제점

이렇게 되면 문제가 있습니다.

함수가 호출이 되면 Stack이라는 공간에

매개변수 , 위치 , 리턴 값이 저장이 되는데

저런 식으로 하게 되면 호출 또 호출하면서 스택에 차곡차곡 쌓이다가

연산이 끝나면 자기 자신을 호출한 애한테 결괏값을 넘겨주는 식인데

여기서 결괏값을 return값이고 자기 자신을 호출한 애한테 넘겨줘야 하니까 위치를 또 기억하고 있어야 한다는 겁니다.

그래서 계속 호출 호출 호출 호출 호출~하게 되면

stack이 넘쳐버려서 Stackoverflow가 발생하게 됩니다. 익숙한 사이트가 생각나죠

 

꼬리 재귀로 보완해보기

아까처럼 결괏값을 결과값을 리턴해서 호출한 함수에 넘겨주고 이런 식이 아니라

계산을 계속하는데 종료 조건이 오면 그대로 값을 리턴해버립니다.

이렇게 되면 넘겨줄 위치도 기억할 필요가 없습니다.

그래서 스택에 차곡차곡 쌓이는 게 아니라 스택 한 줄에 덮어버립니다.

주의할 점

1. 최적화

꼬리 재귀 최적화를 지원하는 언어가 있고 안 하는 언어가 있기 때문에

최적화를 지원 안 하는데 꼬리 재귀를 써버리면 그냥 의미가 없어요

 

2. 잘 쓰기

전 글에서 말한 거처럼 재귀 함수의 장점은 변수 선언을 줄일 수 있다는 거였는데

꼬리 재귀를 사용하면서 매개변수가 하나 늘었죠

생각을 잘하면서 써야 해요