[Algorithm] Fibonacci

1. 정답만 보고 싶다면 <-- (클릭)

2. 잡담

 

 

여름이었다...

재귀 함수에 대해 공부하다가 FIbonacci를 보았고 백준에 있는 문제를 풀어보았다 10870번

 

일단 최대한 고민해보며 재귀 함수를 어떻게 사용할까 생각하며 풀었다

 

고민의 흔적을 증거로 제출하겠다

고민의 흔적들

그래서 어떻게 풀었는데?

def Fibo(n, f1, total):
    if n > 0:
        print(n, f1, total)
        return Fibo(n-1, total, total+f1)
    else:
        return total

print(Fibo(int(input()), 1, 0))

재귀 함수를 공부하며 꼬리 재귀 함수를 알게 되었고 어떻게 응용할 수 없나 고민하다 만들어 버렸다

 

 

그런데 큰 문제가 생겼다 내가 풀었지만 내가 잘 모르겠다.... 큰일이다....

코드를 적으면서 어 될 것 같은데??라는 생각을 하며 적어 내려갔다 근데 진짜 됐다 

 

이럴 때가 제일 난감하다  내가 쓴 코드를 이해하지 못하면 난 잠을 잘 수가 없다 

 

설명할 것들 리스트

1.  코드 1번 줄부터 마지막 줄까지 이 줄을 사용한 이유를 설명하라

 

 

#1 다시 돌아왔다 

 

그림 1

일단 답은 다 맞게 나오긴 한다 100을 입력하면 354224848179261915075가 잘 나온다

근데 도저히 이해를 못 하겠다 내가 뭘 갑자기 생각해서 저런 코드가 나왔는지....

 

# 2 다시 돌아 왔다

뮈첬다 이해해 버렸다

그림 2

이런 식으로 재귀가 일어나 나는데 [그림 1]을 다시 보고 와주면 좋겠다!!

 

이 재귀는 처음 함수를 시작하는 부분이 시작이 아니라 두 번째 즉 

인자 값으로 (n = 4, F1 = 0, Total = 1)이 들어왔을 때부터 그림 2의 순서가 나온다

 

그럼 이런 질문이 나올 수 있다

"왜 함수 첫 번째부터 시작하는 게 아니죠?"

나도 모르겠.... 다

왜 이런 코드가 갑자기 툭 나온 걸까......

 

#3 다시 왔다

def Fibo(n, f1, total):
    if n > 1:
        print(n, f1, total)
        return Fibo(n-1, total, total+f1)
    else:
        return total

print(Fibo(int(input()), 0, 1)) # <-- (1,0) 에서 (0, 1)로 바꿈
#그럼 처음 부터 됨

이렇게 하면 처음부터 간다