순환 Recursion, 재귀함수 알고리즘

본 포스팅은 Inflearn 강의를 듣고 학습한 내용을 정리한 것입니다.

https://inf.run/Jxmd

[무료] 영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런 | 강의

 

순환 (Recursion)

자기 자신을 호출하는 함수로 재귀함수라고도 한다.

void func() {
	...
    func();
}

 

• 무한 루프에 빠지는 경우

재귀함수는 자기 자신을 호출하는 함수로 아래의 코드와 같은 경우 무한 루프에 빠진다.

void func() {
	System.out.print("Repeat");
    func();
}

• 무한 루프에 빠지지 않는 경우

Recursion이 무한 루프에 빠지지 않는 함수는 2가지 조건을 만족해야 한다.

 

1. Base Case가 적어도 하나 이상 존재해야 한다.

Base Case는 재귀 호출에 빠지거나, 재귀 호출을 일으키지 않는 재귀함수의 기본 케이스를 의미한다.

즉, Recursion에 빠지지 않는 경우가 적어도 하나 이상 존재 해야한다.

 

2. 순환을 반복하면 Base Case로 수렴하는 Recursion Case가 존재해야 한다. 

void func(int k) {
	if(k <= 0)  // Base Case
    	return;
    else
    	System.out.print("Repeat");
    	return func(k-1); // Recursion Case
}

 

재귀함수는 논리구조는 수학적 귀납법과 비슷한 구조이다.

피보나치 수 (Fibonacci Number)

public static int fibonacciNumber(int n) {
	if (n == 0)
    	return 0;
    else if (n == 1)
    	return 1;
    else
    	return fibonacciNumber(n-1) + fibonacciNumber(n-2);
}

// n > 2일 경우
public static int fibonacciNumber(int n) {
	if (n < 2)
    	return n;
    else
    	return fibonacciNumber(n-1) + fibonacciNumber(n-2);
}

 

모든 순환 함수는 반복문(Iteration)으로 변경가능하다. 

역으로 모든 반복문은 Recursion으로 표현 가능하다.

순환 함수의 장점은 복잡한 알고리즘을 단순하고 알기 쉽게 표현이 가능하지만, 단점으로 반복된 함수 호출에 따른 오버헤드가 발생할 수 있고, 반복문에 비해 느리다.

 

그럼 어떨 때 순환 함수를 사용해야 할까?

 

순환 함수는 코드를 가독성있게 만들어주고, 변수의 범위를 제한하고 사용을 줄여주어 오류의 발생을 줄여준다. 강의에서는 

암시적(Implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라

라고 설명해준다.강의에 나온 최대값 찾기 예제를 살펴보면 매개변수를 명시적으로 표현하여 알고리즘을 이해하기 쉽도록 구현할 수 있다. 

    public static int findMax(int[] data, int begin, int end) {
        if (begin == end)
            return data[begin];
        else
            return Math.max(data[begin], findMax(data, begin+1, end));
    }

컴파일러에서 꼬리재귀 함수 최적화를 지원하는 경우, 의미를 더욱 명료하고 단순하게 구현할 때 재귀함수를 사용할 수 있다.

꼬리재귀 함수는 재귀함수 호출이 끝난 후 추가연산이 요구되지 않도록 구현한 형태이다.