재귀 함수의 완벽한 이해

재귀 함수란 자기 자신을 다시 호출하는 함수를 말한다.

하지만 이러한 개념을 알고 있어도 직접 구현할려고 하면 헷갈린다.

 

특히, 분기를 위한 반복문이 함수내에 들어간다면 더더욱 그렇다.

 

거리 계산 다이어그램을 예로 해서 살펴보자

 

 

 

 

위 다이어그램의 숫자들은 각 점끼리의 거리이다.

즉, 총 거리는 숫자들을 모두 더한 13이고,

D까지는 3 + 2 + 4 = 9가 된다.

 

재귀 함수로 코드화 해보자 

 

private static int NAME_A = 0;
private static int NAME_B = 1;
private static int NAME_C = 2;
private static int NAME_D = 3;
private static int NAME_E = 4;
private static int NAME_F = 5;
private static int NAME_G = 6;
private static int NAME_H = 7;

 

private int getDistance(int[] points, int index, int searchindex, int distance) {
    //거리 누적
    distance += points[index];
    Log.d("MyLog", "getDistance: " + distance);

    //목적지까지 도착하면 멈춤
    if(index == searchindex)
        return distance;

    //다음 점으로 재귀 호출
    return getDistance(points, ++index, searchindex, distance);
}

 

//점의 거리 배열
int[] points = {0, 3, 2, 4, 3, 1};

//D까지의 거리 계산
int distance = getDistance(points, NAME_A, NAME_D, 0);

Log.d("MyLog", "Distance: " + distance);

 

결과 :

 

D/MyLog: getDistance: 0

D/MyLog: getDistance: 3

D/MyLog: getDistance: 5

D/MyLog: getDistance: 9

D/MyLog: Distance: 9

 

 

 

여기까지는 원래 반복문 하나로도 구현 가능하다

하지만 중간에 분기가 포함되면 재귀 함수의 면모가 드러난다

 

 

 

위 다이어그램은 C에서 두갈래로 갈라진다

코드로는 재귀 함수에 반복문을 추가해준다

 

//점 거리 클래스
private class Point {
    public Point[] mNextPoint;
    public int mDistance;

    public Point(int distance, Point[] nextpoint) {
        mDistance = distance;
        mNextPoint = nextpoint;
    }
}

 

private int getDistance(Point point, Point searchpoint, int distance) {
    while (true) {
        //거리 누적
        distance += point.mDistance;
        Log.d("MyLog", "getDistance: " + distance);

        //목적지까지 도착하면 멈춤
        if (point == searchpoint)
            return distance;

        //다음 점 찾기
        Point[] nextpoints = point.mNextPoint;
        if(nextpoints == null) {
            //더이상 길이 없으면 종료
            break;
        }
        else {
            for (int i = 0; i < nextpoints.length; i++) {
                if(i == 0) {
                    //첫번째 길은 계속 반복문을 돌림
                    point = nextpoints[i];
                }
                else {
                    //두번째 길부터는 재귀 호출
                    int result = getDistance(nextpoints[i], searchpoint, distance);

                    //목적지를 찾았을때에만 누적 거리 반환
                    //그렇지 않으면 이어서 반복문을 돌림
                    if(result >= 0)
                        return result;
                }
            }
        }
    }

    return -1;
}

 

//점의 거리 배열
Point[] points = new Point[8];
points[NAME_H] = new Point(3, null);
points[NAME_G] = new Point(2, new Point[] {points[NAME_H]});
points[NAME_F] = new Point(1, null);
points[NAME_E] = new Point(3, new Point[] {points[NAME_F]});
points[NAME_D] = new Point(4, new Point[] {points[NAME_E]});
points[NAME_C] = new Point(2, new Point[] {points[NAME_D],points[NAME_G]});
points[NAME_B] = new Point(3, new Point[] {points[NAME_C]});
points[NAME_A] = new Point(0, new Point[] {points[NAME_B]});

//A에서 G까지의 거리 계산
int distance = getDistance(points[NAME_A], points[NAME_G], 0);
Log.d("MyLog", "Distance G: " + distance);

//A에서 E까지의 거리 계산
distance = getDistance(points[NAME_A], points[NAME_E], 0);
Log.d("MyLog", "Distance E: " + distance);

 

결과 : 

 

D/MyLog: getDistance: 0

D/MyLog: getDistance: 3

D/MyLog: getDistance: 5

D/MyLog: getDistance: 7

D/MyLog: Distance G: 7

 

D/MyLog: getDistance: 0

D/MyLog: getDistance: 3

D/MyLog: getDistance: 5

D/MyLog: getDistance: 7

D/MyLog: getDistance: 10

D/MyLog: getDistance: 9

D/MyLog: getDistance: 12

D/MyLog: Distance E: 12

 

 

 

재귀 함수의 핵심은 반환값이다.

 

본류와 지류를 구분해 놓고

본류는 반복문이 계속 되게 놔두고 지류만 재귀 호출을 한다.

그리고 성공인지 실패인지 반환값을 받아 계속할지 끝낼지 

결정하면 된다. 

 

 

 

 

 

 

 

 

도움이 되셨다면~ 정성으로 빚은 저희 앱!  많은 이용 바래요:)

 

https://meorimal.com/index.html?tab=spaceship

우주선 - 방치형 인공지능 투자 체험기

 

https://meorimal.com/subway.html

지하철어디있니