10 재귀를 사용한 재귀적 반복

재귀

• 함수가 자기 자신을 호출할 때를 뜻하는 용어
• 올바르게 사용하면 까다로운 문제유형을 간단하게 풀 수 있다.

루프 대신 재귀

 

• 루프를 사용할 수 있는 경우라면 거의 대부분 재귀도 쓸 수 있다.
• 재귀를 쓸 수 있다고 무조건 재귀를 써야한다는 것은 아니다.

기저 조건

위의 코드는 무한대로 음수를 출력하므로

재귀가 무한호출 되지 않게 하는 기저조건이 적어도 하나는 있어야한다.

수정된코드

재귀코드읽기

.1. 기저조건을 찾는다. 2. 기저조건에서 함수가 어떻게 동작하는지 살핀다. 3. "끝에서두번째" 조건을 찾는다. 곧 보이겠지만 이는 기저조건 바로 전 조건이다. 4 .끝에서두번째" 조건에서 함수가 어떻게 동작하는지 살핀다. 5. 방금 분석한 조건의 바로 전 조건을 찾아가며 위 절차를 반복하고 그 때마다 함수가 어떻게 동작하는지 살핀다.

호출스택

스택을 사용해 어떤 함수를 호출중인지 기록

1. factorial(3)이 먼저 호출된다. 완료하기전에.. 2 . f a c t o ri a l ( 2 ) 가 두 번 째로 호 출 된 다 . 완료 하기 전 에.
2. factorial(1)이 세번째로 호출된다.
3. factor ial(1)이 먼저 완료된다.
4. factorial(2)가f actorial(1)의결과를토대로완료된다.
5. 끝으로factorial(3)이factorial(2)의결과를토대로완료된다.

• 호출스택을 통해 값 위로 전달하기 라고도 부른다

스택오버플로

무한재귀에서는 컴퓨터가 반복해서 같은함수를 호출스택에 푸쉬,

더이상 저장할 공간이 없을 때 까지 호출스택은 늘어난다.

= 스택오버플로 라는 오류가 발생한다.

파일 시스템 순회

몇단계나 깊이 들어가야할지 모르는 상황에서 문제를 여러단계로 파고들어야할 때 재귀함수가 잘 들어맞는다.