파이썬 공부일지 18. 함수의 활용(재귀함수)!

 

 

 

이제부터는 앞서 배운 함수를 어떻게 활용하는지에 대해서 공부합니다. 

 

1. 재귀함수

 

재귀함수는 함수 내부에서 같은 기능을 사용하는 거예요. 

재귀는 자기 자신을 호출한다는 의미를 가지고 있습니다. 

 

가령 팩토리얼 이라는 연산자가 있는데 이것을 구하는 것으로 예제를 활용해볼게요. 

팩토리얼은 n!  의 기호로 사용합니다. 

 

n! = n * (n-1) * (n-2) * (n-3) ... * 1 

 

이렇게 연산을 이어가는 것을 팩토리얼이라고 합니다. 

 

ex) 5! = 5 * 4 * 3 * 2 * 1

 

이렇게 팩토리얼을 구현화할 때, 반복문으로 팩토리얼을 구하거나 재귀 함수로 팩토리얼을 구할 수 있습니다. 

먼저 반복문으로 구해볼게요. 

 

 

def factorial(n):     -> factorial () 함수를 만들어줍니다. 
    output = 1         -> 팩토리얼은 곱셈이기 때문에 초기값은 0 이 아닌 1 이 됩니다. 

    for i in range(1, n+1):      -> 범위는 (1부터 n번째가 되는데, 파이썬은 범위의 맨 마지막 인덱스는 세지 않으므로 +1 을 붙여줍니다.) 

        output *= i     그리고 나서 i의 값을 곱하고 그 값을 다시 i로 저장하는 식으로 반복해줍니다.

 

즉 range의 범위가 1에서 5까지라고 한다면 반복되면서 1 * (1+1) * (1+1+1) * (1+1+1+1) * (1+1+1+1+1)로 반복 됩니다.   

1 * 2 * 3 * 4 * 5  로 반복되는 거예요. 

    return output        -> 그 뒤에 output의 값을 출력하며 함수를 시작한 처음으로 돌아갑니다. 

그럼 이제 재귀함수로 구해볼게요. 

팩토리얼은 수식으로 표현하자면  다음과 같습니다. (물론 표현할 수 있는 방법은 무수히 많아요!) 

 

factorial(n) = n * factorial(n-1)     (n>= 1 일 때) 

factorial(0) = 1

 

 

---

그럼 여기서 재귀 표현으로 팩토리얼을 계산하는 코딩을 해볼게요. 

반복문을 사용하는 것보다 재귀 표현으로 사용하는 것이 코드가 더 짧아졌습니다. 

하지만 재귀 함수는 상황에 따라서 기하급수 적으로 많이 반복할 수 있는 문제가 있으므로 사용할 때 유의해야해요. 

 

재귀 함수를 하나 더 살펴보자면, 피보나치 수열이 있습니다. 

이런 식으로 첫 번째와 두 번째 항은 반드시 1이고 그 뒤에는 앞의 항과 그 앞의 항을 더한 값이 되는 수열입니다. 

1번째 수열 = 1 

2번째 수열 = 2

n번째 수열 = (n-1)번째 수열 + (n-2)번째 수열 

 

이를 코드로 구현해보면 

 

  
def fibonacci(n):
    if n == 1 :
        return 1
    if n == 2 :
        return 2
    else :
        return fibonacci(n-1) + fibonacci(n-2)  

 

가 되겠죠. 

그런데 이것은 문제가 있습니다. 피보나치 수열을 구하는  n의 값에 35를 입력할 경우에 시간이 오래 걸립니다. 

숫자가 그보다 더 늘어날 경우에는 60이라고 할 때에는 1시간이 훨씬 넘게 걸려요.

같은 것을 여러번 연산하기 때문에 시간이 오래 걸리는 거예요. 

덧셈 횟수가 기하급수적으로 늘어나기 때문에 계산에 시간이 오래 걸립니다. 

예를 들어 35번째 피보나치 수를 구할 때에는 덧셈을 18454929번 반복해요. 

 

이러한 문제로 인해 재귀함수를 사용할 때에는 메모화를 통해 코드를 간결하고 빠르게 실행합니다. 

값을 새로 계산하는 것이 아니라 값을 메모해두었다가 그것을 불러오는 방식이에요. 

값을 저장해두는 곳은 딕셔너리입니다. 

직접 확인해볼게요. 

# 메모 변수 딕셔너리를 만들어요.

dictionary = {

    1: 1,

    2: 1

}

# 함수를 선언해요.

def fibonacci(n):

    if n in dictionary:

        # 메모에 값이 있으면 메모된 값을 리턴합니다.

        return dictionary[n]

    else:

        # 메모에 값이 없으면 값을 구합니다.

        output = fibonacci(n-1) + fibonacci(n-2)

        dictionary[n]=output

        return output

# 함수를 호출할게요.

print(fibonacci(50))

이렇게 하면 메모한 값이 있을 경우 딕셔너리에 값을 저장하기 때문에 새로운 수열이 발생했을 때 

다시 계산하는 일 없이 메모에 있는 값을 불러오기 때문에 계산식의 속도가 보다 빨라집니다.

 

재귀함수는 조심해서 써야겠어요.. 

 

 

---

2. 리스트 평탄화하는 재귀함수

 

리스트 평탄화는 중첩된 리스트가 있을 때 중첩을 모두 제거하고 풀어서 1차원 리스트를 만드는 것입니다. 

가령 2차원의 리스트가 있다면 (리스트 안에 리스트가 있는 리스트) 이것을 평탄화 시키는 방법은 편합니다. 

a = [1,2,[3,4,],5,[6,7],[8,9]]

# 빈 리스트를 만들어줍니다. 여기에 담을 거예요.

output= []

# 반복문을 통해 리스트 안에 있는 값들을 output 빈 리스트에 담아주는데

for i in a :

    # 만약 담으려는 값이 리스트라면 다시 반복문을 통해 그 안을 꺼내요.

    if type(i) == list:

       

        # 그 뒤에 그 요소들을 output 빈 리스트에 담아줍니다.

        for j in i :

            output.append(j)

    # 만약 담으려는 값이 리스트가 아니라면 그냥 output 빈 리스트에 담아줍니다.

    else:

        output.append(i)

       

print(list(output))

 

 

값은 요로케 나와요 

 

 

하지만 여기서 단점은 3차원의 리스트가 된다면 같은 과정을 여러번 반복해서 리스트를 평탄화 해야한다는 거예요. 

그래서 이럴 때 재귀함수를 쓰면 편리하게 평탄화를 할 수 있습니다. 

a = [1,2,[3,4,],5,[6,7],[8,9]]

# 함수를 만듭니다.

def flatten(data):

    output = []

    # 데이터에 입력된 값을 반복문을 통해 하나씩 꺼내고

    for i in data:

        #그 값이 리스트일 경우에 그 값을 다시 반복문을 통해 하나씩 꺼내서 output 에 넣습니다.

        if type(i) == list:

            output += flatten(i)

        #그 값이 리스트가 아닐 경우에는 그냥 저장합니다.

        else:

            output.append(i)

    return output

   

print(flatten(a))

이렇게 하면  if 구문에서 그 값이 리스트가 아니게 될 때까지 재귀함수를 통해 계속 flatten() 함수가 반복되다가

비로소 리스트가 아니라 값이 나왔을 때 output 에 저장이 됩니다. 

n차원의 리스트 평탄화의 경우 이렇게 사용하면 편리합니다. 

 

 

여기까지 재귀함수의 활용에 대해서 배웠어요.

그 뒤에는 연습 문제가 있었는데, 저는 아직 해결하는 능력이 부족해서 못 푼 문제가 있습니다. ㅠㅠ 

답을 봐도 잘 이해가 안되는 문제였는데 혹시 아시는 분 계시면 알려주세요.. 

 

Q. 사람들을 그룹에 넣습니다. 한 사람만 있는 그룹은 없어야 하고 최대 모일 수 있는 그룹은 열 명입니다. 

인원 수를 나누는 경우의 수를 구해야하는데, 예를 들어 6명이 앉는다고 한다면 

2+2+2   /   2+4   /   3+3   /   6

이런 식으로 경우의 수를 만듭니다. 

100명의 사람이 하나 이상의 그룹에 나누어 앉는 패턴을 구하는 것을 재귀함수와 리턴을 통해서 풀어야 하는데요. 

ㅜㅠ 너무 어렵네요... 궁금하신 분들을 위해 댓글에 풀이를 적어둘게요..