[Python] 재귀함수, 피보나치 수열, 메모화, 리스트 평탄화

---

1. 재귀함수

1) 팩토리얼  factorial

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

 

 👾  이러한 팩토리얼을 구하는 방법은 2가지로 구분

       a. 반복문 사용

       b. 재귀 함수 사용

 

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

def factorial(n):
    output = 1
    for i in range(1, n+1):
        output *= i
    return output

print("1!:", factorial(1))
print("2!:", factorial(2))
print("3!:", factorial(3))
print("4!:", factorial(4))
'''
1!: 1
2!: 2
3!: 6
4!: 24
'''

 

 

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

   - 재귀 recursion 란 '자기 자신을 호출하는 것'을 의미

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

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
        
print("1!:", factorial(1))
print("2!:", factorial(2))
print("3!:", factorial(3))
print("4!:", factorial(4))

 

---

 

2. 피보나치 수열  Fibonacci numbers

 

👩🏻‍💻  피보나치 수를 처음 연구한 것은 레오나르도 피오나치로 토끼 수의 증가에 대해서 이야기하면서 이 수에 대해 언급했다 

   

  📌  n 번째 달의 토끼 수는

• 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.
• 두 달 이상이 된 토끼는 번식 가능하다.
• 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
• 토끼는 죽지 않는다.

출처 : commons.wikimedia.org

 

 

    📌  1번째 수열 = 1

           2번째 수열 = 1

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

 

def fibonacci(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
        
print("fibonnaci(1):", fibonacci(1))
print("fibonnaci(2):", fibonacci(2))
print("fibonnaci(3):", fibonacci(3))
print("fibonnaci(4):", fibonacci(4))
'''
fibonnaci(1): 1
fibonnaci(2): 1
fibonnaci(3): 2
fibonnaci(4): 3
'''

 

count = 0

def fibonacci(n):
    print("fibonacci({})를 구합니다.".format(n))
    global count
    count += 1
    
    if n == 1:
        return 1
    if n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
        
 fibonacci(10)
 print("---")
 print("fibonacci(10) 계산에 활용된 덧셈 횟수는 {}번입니다.".format(count))
 '''
fibonacci(10)를 구합니다.
fibonacci(9)를 구합니다.
...생략...
fibonacci(1)를 구합니다.
fibonacci(2)를 구합니다.
---
fibonacci(10) 계산에 활용된 덧셈 횟수는 109번입니다.
'''

 

💡  위와 같이 덧셈 횟수가 기하급수적으로 늘어나는 이유

 

 

 👾  다음과 같은 형태의 그림을 트리 tree 라고 한다.

 👾  트리에 있는 각각의 지점을 노드 node, 마지막 단계의 노드를 리프 leaf 

     ➡️  트리 내부에 있는 각각의 노드 값을 계산하려면 덧셈을 한 번씩 해야 함

      ➡️  한 번 구한 값은 그것으로 계산이 끝나는 게 아니라,

            한 번 구했던 값이라도 처음부터 다시 계산해야 함

      ➡️  이 때문에 계산 횟수가 기하급수적으로 늘어나는 것

 

 

---

 

💡 위의 예제에서 global count를 쓰는 이유

   

    - 파이썬은 함수 내부에서 함수 외부에 있는 변수를 참조하지 못한다.

    - 함수 내부에서 함수 외부에 있는 변수라는 것을 설명하려면 다음과 같은 구문을 사용해야 UnboundLocalError가 발생하지 않는다.

global 변수 이름

 

---

 

3. 메모화

👩🏻‍💻  한 번 계산한 값을 저장해 놓은 후, 이후에 다시 계산하지 않고 저장된 값을 활용하는 기술

# 메모 변수 생성
dic = {
    1: 1,
    2: 1
}

def fibonacci(n):
    if n in dic:
        # 메모가 되어 있으면 메모된 값을 리턴
        return dic[n]
    else:
        # 메모가 되어 있지 않으면 값을 구함
        output = fibonacci(n-1) + fibonacci(n-2)
        dic[n] = output
        return output
# 함수 호출        
print("fibonnaci(10):", fibonacci(10))
print("fibonnaci(20):", fibonacci(20))
print("fibonnaci(30):", fibonacci(30))
print("fibonnaci(40):", fibonacci(40))

 

 

👾  딕셔너리를 사용해서 한 번 계산한 값을 저장, 이를 메모한다고 표현

👾  딕셔너리에 값이 메모되어 있으면 처리를 수행하지 않고 곧바로 메모된 값을 돌려주면서 코드 속도를 빠르게 만든다.

 

---

 

4. 리스트 평탄화

👩🏻‍💻  중첩된 리스트가 있을 때 중첩을 모두 제거하고 풀어서 1차원 리스트로 만드는 것을 의미

 

def flatten(data):
    output = []
    for item in data:
        if type(item) == list:
            output += flatten(item)
        else:
            output.append(item)
    return output
    
 example = [[1,2,3], [4,[5,6]], 7, [8, 9]]
 print(flatten(example))
 # [1, 2, 3, 4, 5, 6, 7, 8, 9]

 

  ⚡️  append() 함수는 매개변수 하나를 리스트의 마지막 요소로 추가

         ➡️ append(리스트_자료형) 형태로 리스트를 전달하면 리스트 전체가 하나의 요소로서 추가됨

  ⚡️  += 연산자는 오른쪽에 있는 '리스트의 요소'를 하나하나 리스트에 추가

 

 

 

 

 

[ 내용 참고 : 책 '혼자 공부하는 파이썬']