Python - 재귀함수.

재귀 함수.

• 팩토리얼.

$n! = n * (n - 1) * (n - 2) * \dots * 1$

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

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

# 함수를 선언.
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))
print('5!:', factorial(5))

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

$n! = n * (n - 1) * (n - 2) * \dots * 1$

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

• 에시 - factorial(4)

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

# 함수를 선언.
def factorial(n):
    # n이 0이라면 1을 리턴.
    if n == 0:
        return 1
    # n이 0이 아니라면 n * (n - 1)!을 리턴.
    else:
        return n * factorial(n - 1)

# 함수를 호출.
print('1!:', factorial(1))
print('2!:', factorial(2))
print('3!:', factorial(3))
print('4!:', factorial(4))
print('5!:', factorial(5))

재귀함수의 문제.

# 함수를 선언.
def fibonacci(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    else:
        return fibonacci(n -1) + fibonacci(n - 2)

재귀함수의 문제(2).

# 변수를 선언.
counter = 0

# 함수를 선언.
def fibonacci(n):
    # 어떤 피보나치 수를 구하는지 출력.
    print('fibonacci({})를 구합니다'.format(n))
    global counter
    counter += 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(counter))

재귀 함수의 문제.

• 트리(tree)
  • 각 지점 : 노드(node)
  • 노드 중 가장 마지막 단계 지점 : 리프(leaf)

재귀 함수의 문제

• 메모화

  • 재귀 함수를 사용하면서 코드가 빠르게 실행되려면?

  • 같은 값을 한번만 계산하도록 코드를 수정.

    # 메모 변수를 만듦.
    dictionary = {
        1 : 1,
        2 : 2
    }
    
    # 함수를 선언.
    def fibonacci(n):
        if n in dictionary:
            # 메모가 되어 있으면 메모된 값을 리턴.
            return dictionary[n]
        else:
            # 메모가 되어 있지 않으면 값을 구함.
            output = fibonacci(n - 1) + fibonacci(n - 2)
            dictionary[n] = output
            return output
    
    # 함수를 호출.
    print('fibonaccil(10) : ', fibonacci(10))
    print('fibonaccil(20) : ', fibonacci(20))
    print('fibonaccil(30) : ', fibonacci(30))
    print('fibonaccil(40) : ', fibonacci(40))
    print('fibonaccil(50) : ', fibonacci(50))

람다.

• 람다 : 기능을 매개변수로 전달하는 코드를 더 효율적으로 작성.

• 함수의 매개변수로 함수 전달.

# 매개변수로 받은 함수를 10번
def call_10_times(func):
	for i in range(10):
		func()

# 간단한 출력.
def print_hello():
	print('안녕하세요')

# 조합
call_10_times(print_hello)

filter() 함수와 map() 함수.

• 함수를 매개변수로 전달하는 대표적인 표준함수.

map(함수, 리스트)
filter(함수, 리스트)

def power(item):
    return item * item
def under_3(item):
    return item < 3

# 변수를 선언.
list_input_a = [1,2,3,4,5]

# map() 함수를 사용.
output_a = map(power, list_input_a)
print('# map() 함수의 실행결과')
print('map(power, list_output_a):', output_a)
print('map(power, list_output_a):', list(output_a))
print()

#filter() 함수 사용.
output_b = filter(under_3, list_input_a)
print('# filter() 함수의 실행결과')
print('filter(under_3, output_b) :', output_b)
print('filter(under_3, output_b) :', list(output_b))

• 람다란 ‘ 간단한 함수를 쉽게 선언하는 방법’

lambda 매개변수 : 리턴값.

power = lambda x: x * x
under_3 = lambda x: x < 3

# 변수를 선언.
list_output_a = [1,2,3,4,5]

#map()함수 사용.
output_a = map(power, list_input_a)
print('#map() 함수의 실행결과')
print('map(power, list_output_a):', output_a)
print('map(power, list_input_a:', list(output_a))
print()

#filter() 함수 사용.
output_b = filter(under_3, list_input_a)
print('# filter(*) 함수의 실행결과')
print('filter(under_3, output_b : ', output_b)
print('filter(under_3, output_b): ',list(output_b))

• 예시 - 인라인 람다.

  • 함수의 매개변수에 람다 곧바로 넣을 수 있음.

    # 변수를 선언.
    list_output_a = [1,2,3,4,5]
    
    # map() 함수를 사용.
    output_a = map(lambda x: x * x, list_input_a)
    print(' # map() 함수의 실행결과')
    print('map(power, list_input_a):', output_a)
    print('map(powerm list_input_a):', list(output_a))
    
    # filter() 함수의 사용.
    output_b = filter(lambda x : x < 3, list_output_a)
    print('# filter() 함수의 실행결과')
    print('filter(under_3, output_b):', output_b)
    print('filter(under_3, output_b):', list(output_b))

• 매개변수가 여러 개인 람다.

lambda x, y : x * y

조기리턴.

• 흐름 중간에 return키워드를 사용.
• if else 조건문 만들고 각각의 마지막 부분에서 리턴하게 할 경우.

# 함수를 선언.
def fibonacci(n):
	if n in dictionary:
		return dictionary[n]
	else:
		output = fibonacci(n - 1) + fibonacci(n - 2)
		dictionary[n] = output
		return output

• 조기 리턴 사용.

def fibonacci(n):
    if n in dictionary:
        return dictionary[n]

    output = fibonacci(n - 1) + fibonacci(n - 2)
    dictionary[n] = output
    return output

제너레이터(발생자).

• 제너레이터는 이터레이터를 생성해주는 함수.
• 함수 안에서 yield라는 키워드 사용.
  • 함수 안에서 yield를 사용하면 함수는 제너레이터가 되며 yield에는 값(변수) 지정.

def number_generator():
	yield 0
	yield 1
	yield 2

for i in number_generator():
	print(i)

대칭수 판단에 대한 문제.

def reverse(n):
    n = str(n)
    return (n[::-1])

def isPalindrome(n):
    n = str(n)
    if n == reverse(n):
        print(True)
        print('대칭수 입니다.')
    else:
        print(False)
        print(reverse(n))

n = input('number : ')
isPalindrome(n)