UNIT 04 (재귀 호출)

팩토리얼 구하기

문제 1부터 n까지 연속한 정수의 곱을 구하는 알고리즘을 만들어라.

방법1

# 연속한 숫자의 곱을 구하는 알고리즘
# 입력 : n
# 출력 : 1부터 n까지 연속한 숫자를 곱한 값

def fact(n):
    f = 1
    for i in range(1, n + 1):
        f = f * i
    return f

print(fact(1))
print(fact(5))
print(fact(10))

방법2 재귀 호출 알고리즘

# 연속한 숫자의 곱을 구하는 알고리즘
# 입력 : n
# 출력 : 1부터 n까지 연속한 숫자를 곱한 값

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

print(fact(1))
print(fact(5))
print(fact(10))

연습문제

4-1) Unit 1의 1부터 n까지의 합 구하기를 재귀 호출로 만들어라.

def fact(n):
    if n <= 1:
        return 1
    return n + fact(n - 1)

print(fact(10))

4-2) Unit 2의 숫자 n개 중에서 최댓값 찾기를 재귀 호출로 만들어라.

#내 해답

def fact(a):
    if a <= 0:
        return v[0]
    return max(v[a], fact(a - 1))

v = [17, 92, 18, 33, 58, 7, 33, 42]
n = len(v)
r = n - 1
print(fact(r))

#교재 해답

def fact(a, n):
    if n == 1:
        return a[0]
    max_n = fact(a, n-1)
    if max_n > a[n-1]:
    	return max_n
    else:
    	return a[n-1]

v = [17, 92, 18, 33, 58, 7, 33, 42]
print(fact(v, len(v)))

4-3) 0과 1부터 시작해서 바로 앞의 두 수를 더한 값을 다음 값으로 추가하는 방식으로 만든 수열을 피보나치 수열이라고 합니다. 즉, 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3이므로 피보나치 수열은 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

피보나치 수열이 파이썬의 리스트처럼 0번부터 시작한다고 가정할 때 n번째 피보나치 수를 구하는 알고리즘을 재귀 호출을 이용해서 구현해라. (힌트: 7번 값 = 5번 값 + 6번 값)

#내 해답

def fact(a):
    if a == 1:
        return 1
    if a == 0:
        return 0
    return fact(a - 1) + fact(a - 2)

print(fact(10))

#교재 해답

def fact(a):
    if a <= 1:
        return a
    return fact(a - 2) + fact(a - 1)

print(fact(10))

출처

모두의 파이썬&알고리즘 합본호 / 이승찬 / 길벗 / 2018-12-10