재귀(Recursion)
자기 자신을 호출하는 함수를 재귀(recursion)라고 부른다.
재귀적 방법은 자신의 복사본을 호출하여 더 작은 문제를 풀게 하여 문제를 해결한다. 이를 재귀 단계(recursion step)라고 부른다.
재귀는 확실히 종료하게 해야 한다.
매 단계마다 함수는 원본 문제보다 조금 더 단순한 문제를 가지고 자기 자신을 호출
작은 문제의 서열은 결국 기본 경우(base case)로 수렴해야 한다.
재귀를 사용하는 이유
재귀 코드는 반복 코드보다 짧고 작성하기 쉽다.
재귀는 비슷한 하위 작업으로 정의될 수 있는 작업에 특히 유용하다.
재귀 함수의 형식
재귀 함수는 하위 작업을 수행하도록 자기 자신을 호출하여 작업을 수행한다.
어느 단계에 이르러서는, 자기 자신을 호출하지 않고도 수행할 수 있는 하위 작업을 수행한다.
이렇게 함수가 재귀 호출하지 않는 것을 기본 경우(base case)라고 하고, 함수가 자기 자신을 호출해서 하위 작업을 수행하는 것을 재귀 경우(recursion step)라고 한다.
재귀와 메모리
재귀 호출될 때마다 메서드(함수, function)의 복사본이 메모리에 만들어진다.
메서드가 종료할 때(즉, 어떤 데이터를 리턴할 때), 리턴하는 메서드의 복사본은 메모리에서 삭제된다.
재귀(recursion)와 반복(iteration) 비교
재귀와 반복 중 어느 것이 더 나은가?
무엇을 하려고 하는지에 따라 다르다
일반적으로 재귀적 접근은 우리가 풀려고 하는 문제를 반영한다
재귀적 접근은 어려운 문제를 쉬게 풀 수 있게 해준다
재귀는 매번 수행하는 재귀 호출에 부가적인 요소들이 추가된다. (스택 공간 등이 필요)
재귀
기본 경우에 도달하면 종료
각 재귀 호출은 스택 프레임(즉 메모리)에 부가 공간을 필요로 한다.
무한 재귀에 들어가면 메모리 용량을 초과해서 스택 오버플로우를 초래한다.
어떤 문제들에 대한 해답은 재귀적으로 수식을 세우기가 쉽다.
반복
조건이 거짓이 될 때 종료한다
각 반복이 부가 공간을 필요로 하지 않는다
무한 루프는 추가 메모리가 필요하지 않기 때문에 무한히 반복된다.
반복적 해법은 재귀적 해법에 비해 간단하지 않을 때가 있다.
재귀에 대한 참고 사항
재귀적 알고리즘에는 두 가지 경우, 재귀적 경우(recursion step)와 기본 경우(basecase)가 있다.
모든 재귀 함수는 기본 경우에 종료해야한다.
일반적으로 반복 해법이 재귀 해법보다 효율적이다.(재귀 호출에 따른 부가적인 메모리 요구 때문)