(Python) 재귀함수 return에 대한 의문 풀이하기

def combinations(n, new_arr, c):
    if len(new_arr) == n:
        arrs.append(new_arr)
        return
    for i in range(c, len(arr)):
        combinations(n, new_arr + [arr[i]], i)

위 코드에서 combinations(1, [], 2) 를 실행하면 전역변수 arrs가 [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7]] 가 된다. 

 

이제 마지막 줄에 return 하나만 붙여보자.

def combinations(n, new_arr, c):
    if len(new_arr) == n:
        arrs.append(new_arr)
        return
    for i in range(c, len(arr)):
        return combinations(n, new_arr + [arr[i]], i)

결과는 [[1, 1]] 이 나온다.

 

 

 

 

 

 

 

 

 

재귀에서 다음 depth의 함수를 실행할 때, 언제 return을 붙여야 하고 언제 붙이면 안 되는지 제대로 이해하지 못하고 살아왔다. (...) 생각보다 총체적인 이해가 필요한 부분이다.

 

 

 

가장 대표적인 재귀함수의 예시인 팩토리얼을 보자.

def factorial(n):
    if n == 1:
        return 1    
    return n * factorial(n - 1)

이 다음에 print(factorial(5))를 실행해서 결과를 출력한다고 해보자. 콘솔에 120이 출력될 것이고, 이는 함수를 작성한 사람의 의도와 일치한다.

그렇다면 이 120은 내부에서 어떤 과정을 거쳐 리턴되었을까?

 

 

 

💡 스택(stack)

함수가 호출될 때마다 파라미터와 지역변수가 저장되는 영역은 스택(stack)이다. 

스택은 함수의 호출과 함께 할당되고, 호출이 완료되면 소멸한다. 

메모리의 높은 주소 → 낮은 주소 순으로 할당되며, LIFO(후입선출) 방식이다.

 

 

 

factorial(5) 를 실행하면 다음과 같은 순서대로 함수가 호출되어 120이 리턴된다.

출처: 파이썬 코딩 도장 https://dojang.io/mod/page/view.php?id=2353

 

다만 이 그림의 위 아래를 뒤집어 생각하면 더 편하다. 실제 운영체제가 제공하는 메모리 공간은 다음과 같다.

재귀함수의 종료 조건을 제대로 설정해주지 않으면, 함수가 계속해서 호출되어 스택 오버플로(Stack Overflow)가 발생한다. 

 

 

다시 처음으로 돌아가보자. 나는 이 함수 때문에 이 게시글을 쓰기 시작했다.

def combinations(n, new_arr, c):
    if len(new_arr) == n:
        arrs.append(new_arr)
        return
    for i in range(c, len(arr)):
        combinations(n, new_arr + [arr[i]], i)

 

Q. 여기서는 왜 함수 안에서 함수를 호출할 때 return을 붙이면 원하는 결과를 얻을 수 없을까?

A. 이 함수는 위 팩토리얼의 예시처럼 '단 한 개의 최종 리턴값'을 계산하는 함수가 아니라, 주어진 배열과 원소 수를 가지고 '가능한 모든 조합'을 만들어 전역변수인 arrs에 추가하는 함수이기 때문이다. 의도 자체가 다르다. 

 

 

 

 

이 combinations 함수에서 재귀 호출에 return을 붙이면 발생하는 일을 보자.

 

(가정) arr = [1, 2, 3, 4, 5] 일 때

combinations(3, [], 0) 실행 → i = 0에서 combinations(3, [1], 0) 실행 → i = 0에서 combinations(3, [1, 1], 0) 실행 → ...

                                                                                                                   → i = 1에서 combinations(3, [1, 2], 1) 실행 → ...

                                              → i = 1에서 combinations(3, [2], 1) 실행 → i = 1에서 combinations(3, [2, 2], 1) 실행 → ...

 

 

이런 식으로 함수가 나뭇가지처럼 쭉쭉 호출된다.

그러다가 함수의 두 번째 파라미터인 new_arr의 길이가 n이 되면 함수가 return을 마주치고, 종료된다.

그런데 이 함수는 리턴값이 없다. 그렇다면 지금까지 함수 호출은 왜 한겨? 그래서 전역변수 arrs에다가 야무지게 리턴 직전에 만들어진 new_arr을 추가했다.

'가능한 모든 조합'을 만드는 함수라서 이 방식으로 처리한 것이다. 

 

 

 

 

 

 

~웬만하면 재귀를 쓰고싶지 않은 마음뿐이다..~