얼거스 개발 일지

📖 책 정보

---

1. 재귀

재귀는 풀이를 더 명확하게 만들어 준다.

재귀를 쓴다고 성능이 더 나아지지는 않는다.

사실 반복문이 더 성능이 좋은 경우가 많다.

이에 대해 스택 오버플로우에 있는 레이 케드웰의 말을 인용해보면 다음과 같이 이야기 할 수 있다.

" 프로그램에 반복문을 사용하면 프로그램의 성능을 향상시킬 수 있지만, 재귀를 사용하면 프로그래머의 능력을 향상시킬 수 있습니다. 상황에 따라 적절한 방법을 골라 사용하세요. "

대부분의 중요한 알고리즘들이 재귀를 사용하므로, 개념을 잘 이해하는 것이 중요하다.

2. 기본 단계와 재귀 단계

재귀 함수를 만들 때는

언제 재귀를 멈출지 알려줘야 한다.

그래서 모든 재귀 함수는

기본 단계 base case 와 재귀 단계 recursive case 라는

두 부분으로 나누어져 있다.

재귀 단계는 함수가 자기 자신을 호출하는 부분이다.

기본 단계는 함수가 자기 자신을 다시 호출하지 않는 경우, 즉 무한 반복으로 빠져들지 않게 하는 부분이다.

java 코드 예시

public class Recursive {

    private void countdown(int i) {
        System.out.println("[ i ]___________🚩  " + i );
		
        // 기본 단계
        if (i <= 1)
            return;

		// 재귀 단계
        countdown(i - 1);
    }
    
    // 실행 확인
    public static void main(String[] args) {
        Recursive r = new Recursive();

        r.countdown(4);

    }
}

실행 결과

[ i ]___________🚩  4
[ i ]___________🚩  3
[ i ]___________🚩  2
[ i ]___________🚩  1

종료 코드 0(으)로 완료된 프로세스

3. 호출 스택

호출 스택은 프로그램에서 중요한 개념이다.

호출 스택은 일반적인 프로그래밍에서도 중요하지만,

재귀를 사용할 때 더욱 중요하다.

스택을 사용하면 편하지만,

모든 정보를 저장해야 하므로 메모리를 많이 소비한다.

함수 호출을 할 때마다 메모리를 사용한다.

스택이 너무 커질 경우

Exception java.lang.StackOverflowError

이런 에러를 만나게 된다.

StackOverFlow 에러를 피하기 위해서는

재귀 대신 반복문을 사용하거나,

꼬리 재귀라는 방법을 사용할 수 있다.

하지만 안타깝게도 자바 언어에서는 꼬리 재귀를 지원하지 않는다.

자바 언어에서 꼬리 재귀를 지원하지 않는 이유 > loosie.tistory