재귀함수와 알고리즘의 관계를 공부하며

재귀함수 학습 목표

• 반복문과 재귀 함수의 차이를 이해하기
• 어떠한 문제에서 재귀적 사고를 통해 문제를 바라보기
• 재귀 함수는 함수가 스스로 함수 자신을 반환하는 동작 원리임을 이해하기
• 재귀 함수의 탈출 조건을 잘 설정하기
• 재귀 함수와 메모리 사용량 간의 관계를 찾아보기
• 꼬리 재귀에 대해 학습하기
• 재귀를 활용한 대표적인 문제인 하노이의 탑 재귀를 찾아보기

재귀함수란 ?

함수가 스스로 함수 자신을 반환하는 동작 원리를 갖는다.

<재귀로 문제를 해결하는 단계> (손풀이 중요 : 손으로, 이론적으로 접근해보기)

(1) 문제를 작게 쪼개기
(2) 문제를 가장 작은 단위로 쪼개기
(3) 문제 해결하기

<장점>

(1) 불필요하게 여러 개의 반복문 사용하지 않기 때문에, 코드 간결 + 수정 용이하다.
(2) 변수 여러 개 사용할 필요가 없다.

<단점>

(1) 코드의 흐름을 직관적으로 파악하기 어렵다.
(2) 반복하여 메서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장한다.
--> 반복문에 비해서 더 많은 메모리를 사용하게 된다.
(3) 메서드를 호출하고 메서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생하게 된다.

< 재귀 함수를 사용하기 위한 조건 >

(1) 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
(2) 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
(3) 변수 사용을 줄여 mutable state(변경 가능한 상태)를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우
(4) 재귀 호출이 종료되는 시점이 존재해야 한다.