[9단계] 재귀

10872. 팩토리얼

 

▼해설보기

1. 재귀함수 코드

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

n = int(input())
print(factorial(n))

 

2. for문 코드

n = int(input())

result = 1
if n > 0:
    for i in range(1, n+1):
        result *= i
print(result)

1. 코드에 대한 전체적인 풀이 내용
*팩토리얼 (=계승) : 1부터 n까지 양의 정수를 모두 곱한 수이다. 0!=1로 약속하고 n!=n*(n-1)! 의 성질을 가진다.
이와 같은 팩토리얼의 특성을 토대로 코드를 작성했다. 0!=1의 성질을 가지기 때문에 입력받는 수가 0인 경우 1을 출력하고 0보다 큰 경우를 조건문으로 만들었다.

*재귀 함수 : 함수 자기 자신을 호출하는 함수를 말한다.

이번 문제는 1부터 입력받은 수까지 의 수를 반복적으로 곱하면 되는 문제여서 for문으로도 작성이 가능하지만 백준 단계별 문제에서 재귀 함수에 포함되는 문제여서 재귀 함수를 이용해서 코드를 작성했다.

 

2. 재귀 함수로 작성한 코드를 풀이한다.
2-1. 코드 상단, 함수를 생성한다.

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

예약어인 def를 이용해서 함수를 생성한다. 함수 이름은 factorial로 하고 입력받는 값은 한 개로 지정했다.
결괏값으로 return 하게 될 변수 이름을 result로 지정하고서 1을 선언했다. 아래에서 if조건식을 n이 0보다 큰 경우로 제한했기 때문에 입력받는 수 n이 0인 경우에는 result 값이 그대로 1로 출력한다.

입력받는 수 n이 0보다 큰 경우에는 팩토리얼이 가진 n!=n*(n-1)! 성질을 이용해서 함수 자기 자신을 불러내서 코드를 작성했다. 이렇게 계산된 값은 result 변수에 선언하여 마지막에 result값을 return 한다.

2-2. 코드 하단부, 입력받는 수를 factorial 함수로 계산한다.

n = int(input())
print(factorial(n))

input함수로 입력받아 정수로 변환한 임의의 수 n은 위에서 생성한 factorial 함수로 계산하여 팩토리얼 값을 출력하도록 코드를 작성했다.

 

---

10870. 피보나치 수 5

 

▼해설보기

1. 재귀함수 코드

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

n = int(input())
print(fibonacci(n))

 

2. for문 코드

n = int(input())

fibonacci = [0, 1]
for i in range(2, n+1):
    num = fibonacci[i-1] + fibonacci[i-2]
    fibonacci.append(num)
print(fibonacci[n])

1. 문제를 풀었던 내용을 전체적으로 정리
이번 문제는 임의의 수가 주어지면 피보나치 값을 출력하는 문제이다. 백준 온라인 저지 단계별 문제풀이에서 재귀 함수 부분에 포함된 문제이기 때문에 재귀 함수로 문제를 풀었고 같은 식을 반복하는 코드를 이용해서 for문으로도 작성해보았다. 피보나치수열과 재귀 함수에 대해 정의한 내용은 아래와 같다.

1-1. 피보나치수열
처음 두 수를 0과 1로 하고 그다음부턴 자기 앞에 두 수를 더한 수의 나열이다. 문제를 풀 때는 피보나치수열의 특성을 그대로 코드로 작성했다. 0과 1은 그대로 출력하고 이후부턴 앞의 두 수를 더한 수가 출력되도록 함수를 작성하였다.

1-2. 재귀 함수
자기 자신을 호출하는 함수이다. 이번 문제는 0과 1을 제외하고 이후의 수를 생성 할 때 재귀 함수를 이용하여 코드를 작성하였다.

2. 재귀 함수를 이용한 코드를 풀이해본다.
2-1. 코드 상단 쪽, 먼저 함수를 생성한다.

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

함수 생성을 위해선 def 예약어를 이용한다. 피보나치수열을 구하는 문제이므로 함수 이름은fibonacci로 지어보았고 임의의 수 n이 주어졌을 때 n번째 피보나치수를 구하는 함수를 생성하기 위해 fibonacci(n)으로 입력받는 값은 n 한 개만 지정하였다. 

if조건식을 이용해서 입력받는 수 n이 1보다 작은 경우, 즉 0과 1인 경우는 그대로 n을 return 하고 0과 1이 아닌 경우에는 앞의 두 수를 더한 값을 return 하도록 하였다. 이때, 앞의 두 수를 불러낼 때 함수 자기 자신을 불러오는 재귀 함수를 이용해서 코들를 작성하였다. 앞의 두 수는 각각 (n-1)과 (n-2)로 나타낼 수 있다.

2-2. 코드 하단, 위쪽에서 생성한 함수를 활용한다.

n = int(input())
print(fibonacci(n))

임의의 수 n을 input 함수로 입력받는다. 입력받는 값은 문자열이므로 숫자로 사용하기 위해 int 타입으로 변환한다. 이후에 위에서 생성한 finobacci 함수를 활용해서 입력받은 수로 return 받는 피보나치수를 출력하도록 한다. 

---

17478번. 재귀함수가 뭔가요?

 

▼해설보기

import sys
input = sys.stdin.readline

def recursion(n):
    print("____"*n + '"재귀함수가 뭔가요?"')
    if n == end:
        print("____"*n+'"재귀함수는 자기 자신을 호출하는 함수라네"')
        print("____"*n + "라고 답변하였지.")
        return
    print("____"*n + '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.')
    print("____"*n + '마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.')
    print("____"*n + '그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."')
    recursion(n+1)
    print("____"*n + "라고 답변하였지.")

end = int(input())
print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")
recursion(0)