혼자 공부하는 파이썬 - 05 함수 ②

05-2. 함수의 활용

 

재귀 함수

팩토리얼을 구하는 방법 ~ 반복문으로 팩토리얼 구하기 / 재귀 함수로 팩토리얼 구하기

 

(1) 반복문으로 팩토리얼 구하기

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

print("2! : ", factorial(2))

 

(2) 재귀 함수로 팩토리얼 구하기

재귀란 '자기 자신을 호출하는 것'을 의미한다. 

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

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

 

 

재귀 함수의 문제

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

    
print("fibonacci(3) : ", fibonacci(3))
fibonacci(3) :  2
print("fibonacci(4) : ", fibonacci(4))
fibonacci(4) :  3

 

counter = 0

def fibo(n) : 
  print("fibo({})를 구한다".format(n))
  global counter
  counter += 1
  if n == 1 :
    return 1
  if n == 2 :
    return 1
  else :
    return fibo(n-1) + fibo(n-2)

fibo(10)
print("----")
print("fibo(10) 계산에 활용된 덧셈 횟수는 {}번 입니다.".format(counter))

 

** UnboundLocalError에 대한 처리

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

(변수에 접근하는 것을 참조라고 함)

함수 내부에서 함수 외부에 있는 변수라는 것을 설명하려면 global 키워드를 사용한다.

global키워드는 파이썬 프로그래밍 언어에만 있는 특이한 구조이다.

 

** 메모화

dict = {
    1: 1,
    2: 1
}

def fibo(n) :
  if n in dict : 
    #메모가 되어 있으면 메모된 값을 리턴
    return dict[n]
  else :
    #메모가 되어 있지 않으면 값을 구함
    output = fibo(n-1) + fibo(n-2)
    dict[n] = output
    return output

print(fibo(10))

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

딕셔너리에 값이 메모되어 잇으면 처리를 수행하지 않고 곧바로 메모도니 값을 돌려주면서 코드의 속도를 빠르게 만듬

뭔소리야

 

 

리스트 평탄화하는 재귀 함수 만들기

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

 

 

---

<확인 문제>

1. 패밀리 레스토랑에서 여러 개의 테이블에 나누어 앉으려고 한다. 이때 한 사람만 앉는 테이블이 없게 그룹을 지어야 함.

인원수를 나누는 패턴만 구하면 되며, 누가 어디에 앉는지 등은 고려하지 않아도 된다. 예를 들어 6명이라면 다음과 같은 네 가지 경우를 생각할 수 있다. 

2명 + 2명 + 2명

2명 + 4명

3명 + 3명

6명

 

한 개의 테이블에 앉을 수 있는 최대 사람의 수는 10명이다. 100명의 사람이 하나 이상의 테이블에 나누어 앉는 패턴의 경우의 수를 구하라. 소스 코드에서 한글 변수명은 식별자 작성 규칙에 따라 이름을 정하면 됨