[Python] 파이썬 기초 8: 함수(3, 4)

함수(3)

재귀함수(Recursive Function)

• 정의: 자기 자신을 호출하는 함수.
• for loop, while loop으로는 해결할 수 없는 문제
• 반복 작업을 깔끔하게 해석 가능
• 비선형 구조(tree)에 대한 자료를 다룰 때

Factorial 함수

• 자연수 n의 factorial은 n보다 작거나 같은 모든 자연수의 곱.
• n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1 = n * (n - 1)!
• 0! = 1

$factorial(n) = 1 (n = 0), otherwise : n *factorial(n-1)$

# factorial formed by for-loop
def factorial(n):
	assert (n>=0)
	fact = 1
	for i in range(1, n+1): 
		fact *= 1
	return fact

# factorial formed by recursive function
def fact_rec(n):
	assert (n >= 0)
		if n == 0: # fact(0) = 1
			return 1
		else:
			return n * fact_rec(n-1) # fact(n) 정의

재귀 함수의 구성

• 기본 조건(Base case): 자기 자신을 호출하지 않는 부분
• 반복 단계(Recursive step): 자기 자신을 호출하는 부분
  • 반복단계만 있다면 무한loop걸리겟지

조건부 return문

def fact_rec_2(n):
	assert n >= 0
		return 1 if n == 0 else n * fact_rec(n-1)

수학적 귀납법

• 모든 자연수 n에 대해 **명제 P(n)**을 수학적 귀납법으로 증명하는 방법.
  • 기본 단계(base case): P(1)이 참임을 증명한다
  • 귀납 단계(inductive step): 1 ≤ n에 대해서, P(n)이 참이라고 가정하고, P(n+1)이 참임을 증명
• 예제 1. 다음 홀수의 합 공식을 증명하라
  1. 기본 단계/ n = 1일 때
     1. LHS(좌변)=1
     2. RHS(우변)=1
     3. 따라서 P(1)은 참이다
  2. 귀납 단계
     1. 1 ≤ n인 모든 자연수 n에 대해 P(n)이 참이라고 가정. 즉, $1 + 3 + 5 + ...+(2n-1)=n^2$ 이 성립한다고 가정.
     $$ P(n+1): 1 + 3+5+...+(2n-1)+(2n+1) = (n+1)^2 $$
  $$ LHS=1+3+5+...+(2n-1)+(2n+1) = n^2 + (2n+1) = (n+1)^2 = RHS $$
• $$ P(n): 1 + 3 + 5 + ... + (2n-1) = n^2, all n>=1 $$

즉, P(n+1)이 참이다.

즉, 모든 자연수 n에 대해서 P(n)이 참이다.

• 예제2. 다음 합 공식을 증명하라

$$ P(n)=1+2+3+...+n=n(n+1)/2 $$

1. 기본 단계: n = 1일 때
   1. LHS=1, RHS=1, 따라서 P(1)은 참이다
2. 귀납 단계
   1. 1 ≤ n 인 모든 자연수 n에 대해 P(n)이 참이라고 가정, 즉, 아래 식이 성립한다고 가정.$$ P(n+1): 1 + 2+3+...+n+n(n+1) = (n+1)(n+2)/2 $$
   2. $$ LHS=1+2+3+...+n+(n+1)=(1+2+3+...+n+)+(n+1) = n(n+1)/2 + (n+1) = n(n+1)/2 + 2(n+1)/2 = n(n+1) + 2(n+1) = RHS $$
   3. $$ 1 + 2+3+...+n=n(n+1)/2 $$

따라서 모든 자연수 n에 대해 P(n)이 참이다.

# 재귀함수 이용, 홀수 합 구하는 프로그램
def sum_of_k_odd_integers_recursive(k):
# base case, p(1)일 때므로 n=1일때 명제P(1)은 참
	if k == 1: 
		return 1

# recursive step, P(n)일때와 P(n+1)일 때를 증명
	else: # recursive step
		return sum_of_k_odd_integers_recursive(k-1) + (2*k-1)

하노이의 탑

• Rules
  • n개의 디스크를 A에서 C로 옮긴다
  • 한 번에 하나의 디스크만 옮긴다
  • 디스크를 세개의 포스트 중 하나에만 놓을 수 있다
  • 크기가 큰 디스크를 크기가 작은 디스크 위에 얹을 수 없다
• 문제 해결 알고리즘
  1. 전체 디스크는 A에 있다
  2. 가장 큰 디스크(1번째)를 제외한 나머지 디스크들을 B에 옮긴다
  3. 가장 큰 디스크(1번째)를 C에 옮긴다
  4. 나머지 디스크들을 전부 C에 옮긴다
• 재귀 함수 이용 알고리즘

def moveDisk(n, from_, to_, via_): 
'''n은 disk 갯수, from은 움직이기 시작한 막대, to는 종착막대, via는 거쳐가는 막대'''
	if n == 1:
		print(f"Move Disk from {from_} to {to_}")
	else: # recursive step
		# 1. 나머지 디스크들을 전부 via에 옮긴다
		moveDisk(n-1, from_, via_, to_)
	  # 2. 가장 큰 디스크를 to에 옮긴다
		moveDisk(1, from_, to_, via_)
		# 3. via에 있던 나머지 디스크들을 전부 to에 옮긴다
		moveDisk(n-1, via_, to_, from_)

moveDisk(4, "A", "C", "B")
# 입력할경우, base case로 돌아오며 움직임이 나올 것

 

함수(4)

함수형 프로그래밍

• 함수형 프로그래밍은 문제를 함수들의 조합으로 해결한다
• Python에서 일부 허용하고 있음
• Python에서 공부해야 하는 이유
  • 다른 사람들이 만든 코드에서 함수형 프로그래밍 기법이 사용된 경우
  • 함수형 프로그래밍 기법을 사용하는 것이 더 효율적인 경우

개념

• 순수 함수(Pure Function)
  • 함수형 프로그램은 순수 함수 만드는 것을 목표로 함, 수학에서 사용하는 함수 생각.
  • 함수의 side-effect 없이 입력에 의해서만 결정되는 함수를 목표로 함.
  • 동일한 입력에 항상 동일한 출력을 반환하는 함수
    • 순수함수 조건출력이 항상 있어야해(return value)
    • 동일해야해
    • 입력이 있어야해
  • 함수의 외부 상태를 변경하지도 않고, 외부 상태에 영향을 받지 않고, 입력을 변경하지 않는 함수
• 재귀(Recursion): for, while loop 대신 recursion으로 반복 구조 구현
  • for loop은 모두 recursion으로 변환 가능.
• 모든 함수들은 일급(first-class) 객체이자 고차 함수
  • 일급 객체: 함수도 일급 객체임
    • 변수에 할당될 수 있는 객체
    • 함수의 parameter로 사용될 수 있는 객체
    • 함수의 return 값으로 사용될 수 있는 객체
  • 고차 함수: 다른 함수를 자신의 parameter로 사용하는 함수
• 함수형 프로그래밍의 변수들은 immutable

순수 함수의 예

• math.sin(x): return sinx.

# 사용자 정의 순수 함수의 예시
def f(x):
	return 2*x + 1

순수 함수가 아닌 예

• random.randint(): a, b 사이 정수 중 임의로 반환. 동일한 입력에 대해 항상 같은 출력 보증X
• print(): 문자열을 stream으로 보내고 어떤 값도 반환X

import random
help(random.randint)
help(print)

gx = 3
def g(x):
	return gx + x + 3
# g(x)는 global variable gx 참조. 
# gx가 변경되는 경우, g는 동일한 입력에 같은 값 반환 X, 순수함수X

객체로서의 함수

• 함수는 또 다른 함수의 parameter/return value로 사용될 수 있다

def f(x):
	return x**2 + 1

def g(x):
	return x**3 + 1

def applier(q, x): 
	return q(x) # q는 함수. 함수 q의 argument로 반환한 함수 반환
 
a = applier(f, 3) # f는 applier라는 함수의 argument로 전달됨. f는 일급 객체, f(3)
b = applier(g, 3) # g도 argument로 전달됨, g도 일급객체, g(3)
# 이 때 applier는 함수를 parameter로 받기 때문에 '고차 함수'
print("a=", a, ", b=", b) # a = 10, b = 28

함수는 일급객체이다

• 변수에 함수를 할당할 수 있다
• 함수는 tuple, list의 일부로 사용될 수 있다

import math
a = math.sin(math.pi/2)
s = math.sin
b = s(math.pi/2) # s를 함수처럼 사용해, sin(pi/2)와 같은 효과,
# 즉, a == b

f = [math.sin, math.cos] # sin, cos를 list f의 element로 사용.
c = f[0](math.pi/2) # f[0]=math.sin이므로, math.sin(pi/2)와 같은 효과.
# math.sin에 argunment로 pi/2를 전달했음.
# 즉, a == c
print(a, b, c) # 1.0, 1.0, 1.0

함수형 프로그래밍에서는 immutable 객체만 사용해야 한다

• python은 절차지향 / 객체지향 / 함수형 프로그래밍 특징 다 지원.

lambda를 이용한 무명함수(anonymous function)

• 함수형 프로그래밍에서는 변수와 함수만을 사용 > 함수 정의할 일 많음.
• lambda 표현형식: 이름없는 함수, 즉 함수 객체를 생성
• 그때그때 이용하고 지워버리는 함수

<aside> 💡 lambda arguments : expression

</aside>

lambda 표현식 다음에 오는 객체는 반드시 return됨.

# keyword def 이용하여 함수 정의
def f(a):
	return a + 10
print(f(5)) # 15

# lambda 표현식
lambda a: a+10 # <function __main__.<lambda>(a)>
# 해당 표현식 자체가 '함수 객체'를 생성하는 것이기 때문에 전체를 함수처럼 이용 가능
(lambda a: a+10)(5) # 15
# 따라서 호출시는 일반적인 함수 호출하는 것처럼 argument 전달해야 함

g = lambda a : a+10
# lambda 표현식 자체가 하나의 함수객체이기 때문에(일급 객체)
# 일급 객체인 이 함수를 변수에 할당할 수 있음
print(g(5)) # 15

# 재귀함수 이용 factorial
def factorial(n):
	return 1 if n == 0 else n * factorial(n-1)

# lambda 표현식 이용 factorial
lambda n:1 if n == 0 else n * factorial(n-1)

(lambda n:1 if n == 0 else n * factorial(n-1))(5) # error
# 무명함수로는 재귀함수 만들 수 없음. 함수 내부에서 다시 호출할 이름이 없기 때문.

# 변수에 lambda 표현식으로 정의할 함수를 저장하고(좌변)
# 내부에서 이 함수를 다시 호출하는 방식으로 만들어야 함(우변)
# 이 lambda 표현식이 함수객체와 binding 되는것.
factorial_lambda = lambda n:1 if n == 0 else n * factorial_lambda(n-1) 
print(factorial_lambda(5)) # 120

# lambda 표현식에 parameter 다수 사용 가능
x = lambda a, b, c: a + b + c
x(1, 2, 3) # 6

# positional, keyword parameter 모두 사용 가능
x = lambda a, /, b=2, *, c=3: a + b + c
x(1, 2, c=3) # 6
x(1, 2, 3) # error

filter 함수

<aside> 💡 filter(function_to_apply, iterable)

</aside>

• 함수의 반환값은 T/F
• iterable 객체 중 True만 모아서 다시 iterable로 반환

ex. list 정수 중 홀수 골라내기

lst = [1, 3, 4, 6, 8, 5, 9]

# for loop 이용
odd_lst=[]
for n in lst:
	if n%2: # 2로 나눈 나머지가 존재하는 경우에만 odd에 append
		odd_lst.append(n)
print(odd_lst) # [1, 3, 5, 9]

# list comprehension 이용
# lambda는 입력 parameter을 2로 나눈 나머지를 return
new_lst = filter(lambda x: x%2, lst)
new_lst # filter at ... > return iterator object
# return된 객체를 list로 만들고 싶다면
list(new_lst) # [1, 3, 5, 9]

# iterator기 때문에 next 이용하면 원소가 하나씩 반환되는 것을 확인 가능
next(new_lst) # 1
next(new_lst) # 3
next(new_lst) # 5
next(new_lst) # 9
next(new_lst) # exception: stopiteration

map 함수

<aside> 💡 map(function_to_apply, iterable)

</aside>

• iterable의 각 원소에 function_to_apply를 적용한 결과를 iterable로 만들어 return.

ex. 리스트 원소의 제곱을 리스트로 반환

lst = [1, 2, 3, 4, 5]
lst_squared = [] 
# for loop 이용
for n in lst:
	lst_squared.append(n**2)

# list comprehension 이용
lst_squared = {n**2 for n in lst]

# map 함수 이용
def square(x):
	return x**2
# lst의 제곱을 모아 iterable로 return
lst_squared = list(map(squared, lst))
lst_squared

# map과 lambda 함수 이용
print(lst) # [1, 3, 4, 6, 8, 5, 9]
lst_squared = list(map(lambda x: x**2, lst))
# 무명함수가 첫 번째 argument로 넣고
# 반환된 iterable을 iterator로 출력했음
print(lst_squared) # [1, 9, 16, 36, 64, 25, 81]

lst_squared = map(lambda x: x**2, lst)
# 반환된 lst_squared가 iterable임을 확인해보기 위해 next 함수 적용
next(lst_squared) # 1

reduce 함수

<aside> 💡 reduce(function_to_apply, iterable[initial])

</aside>

• folding/reduction을 구현한 함수
• 원소들이 나열되어 있을 때, 원소들을 하나의 누적 값으로 바꾸는 함수

1~5합 구하기

# for loop 이용
lst = range(1, 6)
total = 0
for n in lst:
	total += n
print(total) # 15

# function reduce 이용
from functools import reduce
total = reduce(lambda a, b: a + b, lst)
# filter, map은 parameter 1개였으나 reduce는 2개! 
# 즉, reduce 함수는 lst[0], lst[1]에 lambda 함수를 적용함.
# 그리고 적용 결과와 lst[2]를 lambda 함수를 적용 ... 
# 결과의 최종 값을 reduce return 값으로 반환
print(total) # 15

$$ ((((1+2)+3)+4+5) $$

reduce 함수를 사용해 factorial 다시 구현

from functools import reduce
def factorial_4(n):
	assert n >= 0
	if n == 0:
		return 1
	else:
		# 1부터 n까지의 곱을 reduce 이용해서 작성할 수 있음
		return reduce(lambda a, b: a * b, range(1, n+1))
factorial_4(1) # 1

a = reduce(lambda x, y: x + y, ['a', 'bb', 'ccc']
# 문자열의 처음부터 끝까지 덧셈을 적용한 결과가 return
print(a) # abbccc

# reduce 함수의 초기값(initial)
reduce(lambda a, b: a + b, range(1, 6), 10) # 25
reduce(lambda a, b: a + b, [], 10) # 10

# reduce 함수에 lambda 표현식 아닌, 일반적 함수를 사용하는 경우
def add_and_print(a, b):
	res = a + b
	print(f"{a} + {b} = {res}")
	# 함수 내에서 문자열 출력 > side effect 발생시키기에 순수 함수X.
	return res
reduce(add_and_print, range(1, 6)) # 15
# reduce 함수는 parameter에 순수함수 아니어도 받아들임

reduce(add_and_print, range(1, 6), 10) # 25

reduce 함수를 이용해 list 내 최댓값, 최솟값 구하기

lst = [1, 5, 2, 7, 8]
reduce(lambda a, b: a if a >= b else b, lst) # 8
# lambda에서 a, b 비교해서 큰 값 반환을 나타냈기 때문에 
# reduce 거치며 가장 큰 값 리턴됨
reduce(lambda a, b: b if a >= b else a, lst) # 1