Chapter 03 - 재귀

재귀(recursion)

- 재귀는 함수가 자기 자신을 호출한다

- 이로인해 무한반복을 하는 함수를 만들기 쉽다.

-재귀함수는 기본단계 => 자기자신을 다시 호출하지 않는 경우(무한반복에 빠지지 않게 해준다)

                   재귀단계 => 함수가 자기자신을 호출하는 부분 

으로 나누어져 있다.

 

스택 

- 스택은 아주 단순한 자료구조이다. 데이터가 가장위에 push 되고 가장위에 데이터가 pull된다.

- 호출스택은 재귀를 사용할 때 매우 중요한 개념이다.

- 컴퓨터는 호출스택이라 불리는 스택을 사용한다. 

 

예시는 의사코드로 작성 (의사코드 : 코드처럼 보이지만 실제로는 우리가 사용하는 말과 비슷한 코드)

위의 그림과 같은 방식으로 여러개의 함수를 호출하면서 함수에 사용되는 변수를 저장하는 스택을 호출 스택이라 한다.

 

재귀 함수에서 호출 스택사용 

보물을 찾기위해 가능한 알고리즘 방법 2개 

 

재귀는 확인해야할 상자더미가 없는데 어떤 상자를 열어야 하는지 확인가능한가 ?

여기서 활용된는 방법이 호출스택 !! 확인해야할 상자가 스택에 저장되어 있다. 스택을 사용하면 확인해야할 상자더미를 추적하지 않아도 된다.

하지만 상자가 너무 많아서  스택이 너무 커지게 된다면? 모든 프로그램은 호출 스택에 할당할 수 있는 공간이 제한되어 있어 스택 오버플로우오류로 프로그램이 종료된다.

 

만약 호출함수가 너무 많을 거 같다면 재귀대신 반복문을 사용하자 .