6. Fibonacci Sequence

Fibonacci Sequence

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144와 같이 앞의 두 수의 합이 뒤의 수가 되는 수의 배열

func fibForNumSteps(_ numSteps : Int) -> [Int] {
    var sequence = [0, 1]

    if numSteps <= 1 {
        return sequence
    }

    for _ in 0...numSteps - 2 {
        let first = sequence[sequence.count - 2]
        let second = sequence.last!
        sequence.append(first + second)
    }

    return sequence
}
fibForNumSteps(8)
//[0, 1, 1, 2, 3, 5, 8, 13, 21]

 

만약 피보나치수열에서 첫 번째나 두 번째 경우까지 반환할 경우 0, 1이기 때문에 조건문에서 1 이하의 수는 변수 sequence에 있는 [0, 1]을 반환시킵니다.

1 이상일 경우 for in 구문이 실행되고 sequence 배열의 가장 첫 번째가 0이기 때문에 sequence.count (2 - 2)로 sequence의 배열 index [0]인 0과 그 뒤 숫자 1을 sequence.last로 불러온 뒤 first + second를 합친 수를 sequence의 배열에 추가시킵니다. 

sequence 배열은 [0, 1, 1] 이 되고 다시 for in 구문의 처음으로 돌아와 sequence.count (3 - 2)로 sequence의 배열index[1]인 1과 그 뒤 숫자 1을 sequence.last로 불러온 뒤 first + second를 합친 수를 sequence의 배열에 추가시킵니다.

sequence 배열은 [0, 1, 1, 2] 이 되고 다시 for in 구문의 처음으로 돌아와 sequence.count (4 - 2)로 sequence의 배열index[2]인 1과 그 뒤 숫자 2를 sequence.last로 불러온 뒤 first + second를 합친 수를 sequence의 배열에 추가시킵니다.  

sequence 배열은 [0, 1, 1, 2, 3] 이 되고 다시 for in 구문의 처음으로 돌아와 sequence.count (5 - 2)로 sequence의 배열index[3]인 2와 그 뒤 숫자 3을 sequence.last로 불러온 뒤 first + second를 합친 수를 sequence의 배열에 추가시킵니다.

이런 식으로 반복하다 보면 피보나치 수열이 완성됩니다.

 

func fibRecursionForNumSteps(_ numSteps : Int, _ first : Int, _ second : Int) -> [Int] {
    
    if numSteps == 0 {
        return []
    }
    print(first, second)
    return [first + second] + fibRecursionForNumSteps(numSteps - 1, second, first + second)
}

[0, 1] + fibRecursionForNumSteps(10, 0, 1)
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

재귀 함수를 통해 간결한 코드를 구성할 수 있습니다. fibRecursionForNumSteps 함수 뒤에 [0, 1] 배열을 놓음으로써 0일 경우 빈 배열을 반환해 [0, 1]을 출력할 수 있게끔 배치해놓았습니다. 

numSteps이 10일 경우 0이 아니기 때문에 조건문을 건너뛰고 [first(0) + second(1)]이 실행되고 다시 fibRecursionForNumSteps를 실행시키고  배열에 더해줍니다.

numSteps는 - 1 이 됨으로 9가 되고, first는 second 인 1이 되고, second는 first(0) + second(1)인 1이 됩니다. fibRecursionForNumSteps를 다시 9,1, 1에 맞게 돌리면 [ first(1) + second(1)] 2가 되고 다시 fibRecursionForNumSteps 함수를 실행시킵니다.

numSteps는 - 1 이 됨으로 8가 되고, first는 second 인 1이 되고, second는 first(1) + second(1)인 2가 됩니다. 

fibRecursionForNumSteps를 다시 8, 1, 2에 맞게 돌리면 [ first(1) + second(2)] 3가 되고 다시 fibRecursionForNumSteps 함수를 실행시킵니다.

numSteps는 - 1 이 됨으로 7가 되고, first는 second 인 2가 되고, second는 first(1) + second(2)인 3이 됩니다. 

fibRecursionForNumSteps를 다시 7, 2, 3에 맞게 돌리면 [ first(2) + second(3)] 5가 되고 다시 fibRecursionForNumSteps 함수를 실행시킵니다.

numSteps는 - 1 이 됨으로 6가 되고, first는 second 인 3이 되고, second는 first(2) + second(3)인 5가 됩니다. 

이를 계속 반복수행하면 피보나치 수열이 완성됩니다.