백준 - 재귀함수가 뭔가요?
in algorithm
재귀 함수 - 재귀함수가 뭔가요?
백준 1478 재귀함수가 뭔가요?
A = int(input())
def fun_recusive(n):
under = "____"
print(under * n + "\"재귀함수가 뭔가요?\"")
if n == A:
print(under * n +"\"재귀함수는 자기 자신을 호출하는 함수라네\"")
return print(under * n + "라고 답변하였지.")
else:
print(under * n + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.")
print(under * n + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.")
print(under * n + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"")
fun_recusive(n + 1)
return print(under * n + "라고 답변하였지.")
print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")
fun_recusive(0)
백준에서 에러가 나와 검색을 하였습니다. 다른 블로그를 참조하니 python3로 제출하면 시간초과가 나오니 pypy3로 제출하라 하셔서 그렇게하니 제대로 정답이라고 나오네요.
재귀함수
이 문제를 푸는데 생각보다 많은 시간이 소요 됐습니다. 문제를 풀때마다 항상 하향식을 생각 하다보니 아래와 같은 구조만을 머리 속으로 생각을 했었습니다.
def fibo(n):
if n == 1 of n== 2:
return 0
else:
return fibo(n-1)+fibo(n-2)
이 문제는 하향식보다는 상향식으로 생각을 바꾸니 아… 이렇게 하면 되는걸 하면서 풀리네요ㅋㅋㅋ.
재귀함수란?
재귀함수는 말 그대로 자기자신을 불러 문제를 해결해 나가는 방식입니다. 유명한 예제로 위 예시의 피보나치가 많이들 사용이 되지요.
피보나치를 해결할때 재귀를 사용하면 시간이 오래 걸립니다. 그냥 예시일 뿐입니다.
재귀함수를 구성하실때는 함수가 끝나는 지점이 존재 해야합니다.
만일, 함수의 끝을 지정해 두지 않는다면? 
def hello():
print("hello\n")
hello()
hello()
보이시나요? 다행이 IDE가 메모리를 오버하기전에 막아줬네요 이 처럼 재귀 함수를 지정하실 때는 끝 나는 지점을 제대로 정해 놓아야 합니다.
피보나치 재귀 함수에서도 끝나는 부분은 제대로 지정해 놓을걸 볼 수 있죠
def fibo(n):
if n == 1 of n== 2: <--- 끝 나는 지점
return 0
else:
return fibo(n-1)+fibo(n-2)
