재귀란

재귀함수란 마치 영화 인셉션에서 꿈속의 꿈속에 들어갔다가, 순서대로 꿈속의 꿈부터 깨어나면서 나오는것과 같다.

재귀함수는 끊임없이 계속해서 본인의 함수를 호출하기 때문에 우리가 함수를 멈추게 장치를 만들어주어야한다.

장단점

장점

• 코드가 간결해지고 수정이 용이하다
• 변수를 여러개 사용할 필요가 없다.

단점

• 반복문과 달리, 코드의 흐름을 추상적으로 생각해야한다.
• 반복하여 메소드를 호출하며, 지역변수, 매개변수, 반환값을 모두 process stack에 저장하게 된다. 그래서 반복문에 비해서 메모리를 더 많이 사용한다.
  -메서드를 호출한 만큼 다시 돌아와야하기때문에 컨텍스트 스위칭 비용이 발생함

사용 조건

• 문제의 크기를 점점 작은 단위로 쪼갤수 있어야함.
• 재귀 호출이 종료되는 시점이 존재해야함.(없을시 무한루프)

내생각

내가 생각할때 재귀는 흐름을 이해하는것이 포인트같다.
그림을 그려서 작은단위로 쪼개면서 그쪼갠값을 또 쪼개서 더이상 쪼갤수 없다면 마지막으로 쪼갠값을 쪼개기 전값에 대입시키면서 계산을 하고, 마지막으로 계산한 값이 우리가 원하는 값이 되도록 로직을 짜는 것이 중요하다.

반복문 vs 재귀

성능상 반복문이 더 좋지만, 특정 상황에서는 재귀가 더 유리하다.

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩회수를 예측하기 어려운경우
• 변수 사용을 줄여 변경 가능한 상태를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우

예시 코드

int []a 의 모든 배열의 합

import java.util.Arrays;


class tryja {
    static int SumArr(int[] a) {
        if (a.length == 0)
            return 0;

        int head = a[0];
        int[] tail = Arrays.copyOfRange(a, 1, a.length);
        return head + SumArr(tail);
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        System.out.println(SumArr(a)); 
    }
}