#1. 재귀함수

[재귀] recursion

문제를 동일한 구조의 더 작은 문제로 나누고, 이 작은 문제를 해결함으로 전체 문제를 해결하는 방법.

재귀함수는 자기 자신을 끊임없이 호출하는 함수를 말한다.

//메소드 바디에 자신의 메소드명을 넣음으로 종료문을 만나기 전까지 계속해서 반복되는 함수

[코드 예제]

public void recursion() {

  System.out.println("This is");

  System.out.println("recursion!");

  recursion();         // 자기 자신을 호출.

}

[재귀함수의 장점]

1. 불필요하게 여러 개의 반복문을 사용하지 않기 때문에, 코드가 간결해지고, 수정이 용이하다.

2. 변수를 여러 개 사용할 필요 없다.

 

[재귀함수의 단점]

1. 반복문과 달리, 코드의 흐름을 직관적으로 파악하기 어렵다.

2. 반복하여 메소드를 호출하며, 지역변수, 매개변수, 반환값을 모두 process stack에 저장.

결과적으로 더 많은 메모리를 사용하게 된다.

3. 메소드를 호출하고, 메소드가 종료된 이후, 복귀를 위한 컨텍스트 스위칭 비용이 발생.

 

[재귀함수 작성 순서]

1. 재귀함수의 종료문을 최상단에 작성해야한다. (재귀함수 종료문 : base case)

2. 문제를 작은 단위로 나누며 최대한 작게 나눈다음 작은 문제부터 해결한다. (재귀함수 작게 쪼갠 경우 Recursive Case]

3. 메서드 바디에 메소드 본인의 이름이 작성되어 호출한다.

 

ex) 문제 : 입력한 숫자 num 과 num부터 1씩 작아지는 정수들의 곱을 구하기.