[파이썬#16] 함수의 활용 (재귀함수, 메모화, 조기리턴)

---

재귀 함수

중학교 수학 시간에는 팩토리얼이라는 연산자를 배운다. 

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

이러한 팩토리얼을 구하는 방법은 두 가지를 구분할 수 있다.

 

 

↘ 반복문으로 팩토리얼 구하기

[실행결과]

곱하기의 초기값은 1 로 설정해야 한다. 

 

 

↘ 재귀 함수로 팩토리얼 구하기

재귀recursion란 자기 자신을 호출하는 것을 의미한다. 팩토리얼 연산은 다음과 같이도 표현할 수 있다.

factorial(n) = n * factorial(n-1) * ... * 1

 

이와 같은 재귀 표현을 factorial(3)을 구해보자. 간단하게 함수 이름은 f로 표현하자.

f(3)
= 3 * f(2)
= 3 * 2 * f(1)
= 3 * 2 * 1

 

→ 재귀 함수를 사용해 팩토리얼 구하기

[실행결과]

 

---

재귀함수의 문제 → 메모화 기술

재귀함수는 상황에 따라서 같은 것을 기하급수적으로 많이 반복한다는 문제가 있다. 그래서 개발자 사이에서는 재귀 함수를 절대 사용하면 안 된다는 의견도 있지만 적재적소에 활용하면 코드를 쉽게 알아볼 수 있다. 재귀 함수로 인해 발생하는 문제를 알아보고, 이후에 이 문제를 해결할 수 있는 메모화memoization라는 기술을 알아보자.

 

재귀함수를 하나 더 살펴보자. 바로 피보나치수열이다. 피보나치수열은 '토끼는 어떠한 속도로 번식하는가' 와 같은 연구에 사용되는 수열이다. 다음과 같은 규칙을 가지고 있다.

 

。처음에는 토끼가 한 쌍만 존재한다.

。두 달 이상 된 토끼는 번식할 수 있다.

。번식한 토끼는 매달 새끼를 한 쌍씩 낳는다.

。토끼는 죽지 않는다고 가정한다.

 

 

한 달이 지날 때마다 달라지는 토끼 쌍의 수를 적어 보면 1쌍, 1쌍, 2쌍, 3쌍, 5쌍, 8쌍, 13쌍, ... 이 된다. 규칙을 적어보면 다음과 같다. 

 

。1번째 수열 = 1

。2번째 수열 = 1

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

 

→ 재귀 함수로 구현한 피보나치 수열(1)

[실행결과]

 

→ 재귀 함수로 구현한 피보나치수열(2)

[실행결과]

PS D:\app\python> python fibonacci_recursion02.py
fibonacci(10)를 구합니다.
fibonacci(9)를 구합니다.
fibonacci(8)를 구합니다.
fibonacci(7)를 구합니다.
fibonacci(6)를 구합니다.
fibonacci(5)를 구합니다.
fibonacci(4)를 구합니다.
fibonacci(3)를 구합니다.
fibonacci(2)를 구합니다.
fibonacci(1)를 구합니다.
fibonacci(2)를 구합니다.
fibonacci(3)를 구합니다.
fibonacci(2)를 구합니다.
fibonacci(1)를 구합니다.
fibonacci(4)를 구합니다.
fibonacci(3)를 구합니다.
...
fibonacci(10):  55
---
fibonacci(10)계산에 활용된 덧셈 횟수는 109번입니다.

fibonacci 함수의 매개변수 값이 커질 수록 실행 시간은 늘어난다. fibonacci(50)을 구할 때는 1시간 넘게 걸린다. 왜냐하면 한 번 구한 값은 그것으로 계산이 끝나면 좋지만, 현재 코드의 재귀 함수는 한 번 구했던 값이라도 처음부터 다시 계산해야 한다. 그래서 계산 횟수가 기하급수적으로 늘어나는 것이다. 

 

 

↘ UnboundLocalError에 대한 처리 - 예외처리- 

재귀 함수로 구현한 피보나치수열(2) 코드에 보면 global counter라는 코드를 사용하고 있는데 왜 이런 코드를  사용하는지 확인하기 위해 다음을 실행해 보자. 

 

→ 재귀 함수로 구현한 피보나치수열(3)

[실행결과]

코드를 실행하면  UnboundLocalError라는 예외를 출력한다. 파이썬은 함수 내부에서 함수 외부에 있는 변수를 참조하지 못한다. 함수 내부에서 함수 외부에 있는 변수라는 것을 설명하려면 아래와 같은 구문을 사용한다.

 

global 변수 이름

 

global 키워드는 파이썬 언어에만 있는 특이한 구조이다. 붉은색 밑줄이 떴을 때 마우스를 올려놓고 W0621: Redefining name 'counter' from outer scope 또는 E0602:Undefined variable 'counter'가 나타나면 global 키워드를 추가해 주면 된다.

 

 

↘ 메모화

재귀 함수를 어떻게 사용해야 코드가 빠르게 실행되도록 만들 수 있을까?

현재 문제는 같은 값을 구하는 연산을 반복하고 있기 때문에 발생하는 것이다. 따라서 같은 값을 한 번만 계산하도록 코드를 수정하면 된다. 

 

[실행결과]

딕셔너리를 사용해서 한 번 계산한 값을 저장한다. 이를 메모한다고 표현한다. 딕셔너리에 값이 메모되어 있으면 처리를 수행하지 않고 곧바로 메모된 값을 돌려주면서 코드의 속도를 빠르게 만드는 것이다. 재귀 함수와 많이 사용되는 기술이므로 꼭 기억하자!

 

 

 

 

---

조기 리턴

과거에는 프로그래밍을 할 때 변수는 반드시 앞쪽에 몰아서 선언하고, 리턴은 반드시 뒤쪽에서 해야 한다는 비공식적인 규칙이 있었다. 하지만 요즘에는 필요할 때 하면 된다는 인식이 널리 퍼졌다. 그럼 return을 중간에 사용하는 형태를 살펴보자. 

 

과거에는 함수 흐름의 끝에 리턴을 적기 위해 메모화 예제 같은 형태를 사용했다. if else 조건문을 만들고 각각의 마지막 부분에서 리턴하도록 한 것이다. 하지만 코드를 다음과 같이 변경하면 어떨까? 들여쓰기 단계가 줄기 때문에 코드를 더 쉽게 읽을 수 있다. 이렇게 흐름 중간에 return 키워드를 사용하는 것을 조기 리턴이라고 부른다. 

 

 

 

 

 

---

(좀 더 알아보기1) 코드에 이름 붙이기

가독성은 프로그래밍할 때 굉장히 중요한 요소이다. 함수로 가독성이 좋은 코드를 작성하는 방법을 살펴보자.

 

예) 원의 둘레와 넓이 구하기

원의 둘레: 2 * 3.14 * radius

원의 넓이: 3.14 * radius * radius

 

우선적으로 주석이 써져 있다면 코드의 내용을 분석하지 않아도 어떤 내용인지 쉽게 이해할 수 있습니다. 그렇다고 주석을 남발하면 안 되고, 주석이 정말 필요한 경우에만 정확히 사용하는 것이 좋다. 

 

→ 주석이 있는 코드

[실행결과]

 

 

→ 함수를 활용한 코드

[실행결과]

 

한 줄의 코드라도 의미를 가지고 있다면 함수로 만드는 것이 좋다. 위의 <함수를 활용한 코드>에서 함수 부분은 모듈이라는 기능으로 더 간단하게 만들 수 있다. 모듈은 나중에~

 

---

(좀 더 알아보기1) 코드 유지보수

함수를 활용하면 코드를 유지보수할 때도 큰 도움이 된다. 바로 직전 코드에서 3.14는 무엇을 의미할까? 물론 당연히 원주율이라고 이야기하는 사람도 있겠지만 그렇지 못한 사람도 있을 수 있다. 그렇다면 이를 변수로 만들어 가독성을 높여줄 수 있다. 

 

코드가 또 길어져서 싫어할 수도 있지만 이와 같이 코드를 작성하면 유지보수에 편하다.

예를 들어, "파이의 정밀로를 올리고 싶어요. 3.141592로 변경해 주세요."라는 요청을 받았다고 가정해 보면 기존 상태에서는 3.14라는 숫자를 찾아 하나하나 변경하거나 전체를 수정해야 한다. 하지만 위와 같이 변수를 사용하면 변수 PI값만 수정하면 된다. 

 

---

연습문제 

<연습문제1>

Q. 다음 빈칸을 재귀 함수로 만들어서 리스트를 평탄화하는 함수를 만들어 보자. 리스트 평탄화는 중첩된 리스트가 있을 때 중첩을 모두 제거하고 풀어서 1차원 리스트로 만드는 것을 의미한다. 

def flatten(data):
                                                       



exam = [[1,2,3],[4,[5,6]],7,[8,9]]
print("원본:", exam)
print("변환:", flatten(exam))

[실행결과]
원본: [[1, 2, 3], [4, [5, 6]], 7, [8, 9]]
변환: [1, 2, 3, 4, 5, 6, 7, 8, 9]

[실행결과]

이 문제를 풀 때는 리스트의 데이터 리스트인지 아닌지 구분할 수 있어야 한다. 

 

 

<연습문제2>

패밀리 레스토랑에서 여러 개의 테이블에 나누어 앉으려고 한다. 이때 한 사람만 앉는 테이블이 없게 그룹을 지어야 한다. 인원수를 나누는 패턴만 구하면 되며, 누가 어디에 앉는지 등은 고려하지 않아도 괜찮다. 예를 들어 6명이라면 다음과 같은 4가지 경우를 생각할 수 있다. 

1) 2명 + 2명 + 2명
2) 2명 + 4명
3) 3명 + 3명
4) 6명

 

Q. 한 개의 테이블에 앉을 수 있는 최대 사람의 수는 10명입니다. 100명의 사람이 하나 이상의 테이블에 나누어 앉는 패턴을 구하라. 

[확인결과]

 

 

 

여기까지.