백준 10870번: 피보나치 수열 5

알고리즘 관련 문제를 풀려고 찾아보다보면 재귀함수에 대한 이야기가 계속 나오는데 한 번도 제대로 써본 적이 없어서 풀게 된 문제

 

재귀함수는 함수 내에서 자기 자신을 다시 호출한다 정도로만 이해한 상태로 시작했다.

계속해서 자신을 호출하기 때문에 종료 조건이 필요하고 계산식이 있는 위치에 따라서 계산하는 값이 달라지는 것 같았다.

 

 

흐름을 따라가 보면

fi_n(3)이 입력이 되면 0보다 크므로

fi_n(3-1)이 실행이 되면서 다시 함수 첫 부분,

 

fi_n(2)도 0보다 크므로

fi_n(2-1)이 실행이 되면서 다시 함수 첫 부분,

 

fi_n(1)도 0보다 크므로 

fi_n(1-1)이 실행

 

fi_n(0) 종료 조건이 충족되었고

앞에서 실행되었던 fi_n(1)에 마지막에 남아있는 print(n)실행후 fi_n(1) 종료

fi_n(2)에 남아있던 print(n) 실행

fi_n(3)에 남아있던 print(n)실행

남아있던 함수 부분이 전부 실행되었으므로 종료

 

처음에 실행되었던 함수가 종료되지 않고 계속 파고파고 들어가다가 안에서부터 하나씩 종료가 되면서 함수가 종료된다.

(사실 아직 이해 못한 것 같다)

 

num = int(input())

rs = 0
def fi_n(n):
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    # fi_n(n-1)
    rs = fi_n(n-1) + fi_n(n-2)
    return rs

print(fi_n(num))

마지막으로 제출해서 정답으로 처리되었던 코드 

오류는 fi_n(n-1)부분의 코드는 전혀 필요없는 부분이었다.