[recursion function] 재귀의 쉬운 이해

TaeSun·2023년 2월 1일

Recursion

[ 재귀 ]

컴퓨터 과학에서 재귀란 문제를 해결하기 위해 그 문제를 작은 경우로 나누어서 푸는 방법을 의미한다.

What is the recursion

재귀는 말그대로 무언가 반복을 의미한다. 컴퓨터 과학에서 말하는 의미를 조금더 나에게 친숙해지도록 표현을 바꿔보자면 "어떤일을 할려고 반복할때 그 문제를 잘게 나누어서 생각해보면 처리하기 쉬울때가 있다"

[트럭에 실려 있는 짐을 다른 트럭으로 옮길때]

물론 트럭에 있는 짐을 한번에 뺄 수 있다면 이보다 더 효율적인 방법은 없겠지만 그렇지 못한다고 가정해본다.

[과정]

[트럭에 있는 짐] -> [여러 사람에게 나누어주자] -> [트럭과 트럭사이 사람끼리 연결 되어 있으니 옮길 트럭쪽에 있는 사람에게 순서대로 나누어주자] -> [옮겨졌다]

한번에 옮기는 것과 나눠서 옮기는 것 두 방법 모두 "짐을 옮기자" 라는 같은 목적이 있다.

Soccer

그럼 축구로 생각해보자 축구를 한번도 해보지 못한 사람이라도 축구라는게 무엇인지만 알고 있다면 이해가 되기 쉬울것이라고 예상해본다.

5명의 선수가 존재한다.

각 선수들은 "패스연습"을 한다고 한다.
패스는 각 선수들끼리 공을 주고 받고 하는 행위를 말하는데 우선 가정을 둔다

5번 선수는 -> 4번 선수에게 패스 가능.
4번 선수 -> 3번 선수
3번 선수 -> 2번 선수
2번 선수 -> 1번 선수

그럼 5번의 선수는 4번에게 공을 차서 공을 넘겨준다 그럼 이 "패스"라는 행위가 끝나게 된다면 현재 5번 선수에게 공은 없고 4번 선수에게 공1개가 존재한다라는 걸 알 수 있다. 마찬가지로 4번은 3번에게 패스를 했을때 3번 선수에게 공이 있다는걸 알 수 있다.
선수가 기하급수적으로 늘어나는게 아니기 때문에 1번째 선수에게 공이 왔다고 가정해보자
그럼 1번 선수를 제외하고 나머지 선수들한텐 공이 없다.
자 그러면 1번 선수는 더 이상 줄 선수가 없기 때문에 다시 돌려주려고 한다.
공을 다시 돌려주는데 그냥 돌려주면 재미 없으니 공을 하나 더 얹어서 준다고 한다.
즉 1번 선수가 가지고 있는 공 1개 + 공 1개 = 공2개를 2번 선수에게 준다는 것이다. 이렇게 모든 선수들이 공을 전달 받게 된다면 1개를 더 얹어서 준다고 생각해보자.
그렇게 된다면 숫자가 작으니 최종적으로 5번 선수가 받을 공의 개수는 ? 5개가 된다. 그 이유는 공의 개수는 한개씩 추가되어서 돌려받기 때문이다.
이걸 코드로 구현해보면 아래와 같이 된다.

Code

def gong(n):
    if n == 1:
    	print("{%d}선수 공의 개수 : {%d}" % (n, 1))
    	return 1
    else:
        goCnt = gong(n-1) + 1
        print("{%d}선수 공의 개수 : {%d}" % (n, goCnt))
        return goCnt
re = gong(5)
print('최종적으로 반환 받은 공의 개수는 : {%d}' % re)

최종적인 공의 개수 : 5개

Result

기술적인 관점

재귀에서는 기저조건 이라는게 존재하는데 기저조건은 재귀가 무한의 빠지지 않게 하기 위해서 최소한의 조건을 걸어두는 것이다. 위 예시에서는 1번 선수에게 도달했을 경우 return 1을 하게 되어있으므로 이게 바로 위 함수에서 기저조건에 해당한다.

함수의 return 문은 함수에서 하나의 값만을 반환하게 된다. 위 함수에서 return 이 두개 작성되어 있다고 해서 return 이 두번 된다는 뜻이 아니다.
자세히 들여다본다면 n!=1 아닌 경우 즉 1번 선수가 아닌 시점에서는 return 1은 하지 않게 되어 있다. 따라서 모든 경우에서 항상 return 은 하나의 값만을 리턴하고 있고 n==1 이 되었을때 비로소 기저조건에 도달하여 기저조건의 해당하는 return 값을 반환하는 것이다.

그럼 패스는 5-4-3-2-1 순으로 패스를 시작했으니 공을 다시 패스할때는 1-2-3-4-5 순으로 공을 반환하므로 2번 선수의 호출시점의 1번 선수의 값을 받고 최종적으로 1번선수의 값을 받게 되었으면 2번 선수의 최종값을 3번 선수가 호출된 시점에서 돌려받고...돌려받고..돌려받고...이렇게 하다보면 위로 올라가면서 gong(1)-gong(2)-gong(3)-gong(4)로 올라가면서
값을 최종적으로 반환하게 되면 재귀의 콜백 구조상 함수가 하나씩 종료가 된다.
쉽게 생각해보면 선수가 다른 선수에게 패스하고 그냥 축구장 나가버리는 것이다.

그렇게 된다면 가장 마지막에 남는 사람이 최종값을 가지고 있는 것이고 최종값을 리턴하고 나면 최종선수의 함수도 종료되게 되는 것이다.