Start learning free

LESSON 282 OF 415 · RECURSION

Recursive Fibonacci in Swift

Practice O(2n) Read the full explanation

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Write a recursive function that given n, returns F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:
  • 0 <= n <= 30
Note:

Don't worry about the time and space complexities of your algorithm.


Hints:

Inside the function, we should first check the base case: if n is less than 2, then we should return n.

If n >= 2, since F(n) = F(n - 1) + F(n - 2), we should return the sum of the recursive calls for n - 1 and n - 2.
STEP 1 OF 2
    Ctrl + Enter to check

    SWIFT · RECURSION

    Recursive Fibonacci in Swift, explained

    Problem overview

    The Fibonacci sequence starts with 0 and 1, and every later number is the sum of the two before it: F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n greater than 1. The sequence runs 0, 1, 1, 2, 3, 5, 8, 13, and so on. The method fibonacci receives n, with 0 <= n <= 30, and must return F(n) using recursion.

    For n = 4 the answer is 3: F(4) = F(3) + F(2) = 2 + 1. Time and space don't matter for this exercise.

    Approach: the definition is the algorithm

    The formula gives a recursive function almost word for word. It has two base cases, F(0) and F(1), and one recursive case that adds the results of two smaller calls.

    The two base cases can be merged. F(0) = 0 and F(1) = 1, so for both of them the answer is n itself. A single check "if n is less than 2, return n" covers both.

    Step by step

    1. Handle the base case first. If n < 2, return n. Without a base case, every call would start two more and the recursion would never stop.
    2. Handle everything else by returning fibonacci(n - 1) + fibonacci(n - 2).

    The solution in Swift

    class Solution {
    func fibonacci(_ n: Int) -> Int {
        if n < 2 {
            return n
        }
        return fibonacci(n - 1) + fibonacci(n - 2)
    }
}

    The Swift details worth a closer look:

    • No argument labels. The parameter is declared as _ n: Int, so the recursive calls are written fibonacci(n - 1), not fibonacci(n: n - 1).
    • The method calls itself by name. Inside the class there is no need for self. in front of the call.
    • Two calls in one expression. Swift evaluates fibonacci(n - 1) first and then fibonacci(n - 2), and adds the two results.
    • Overflow. Int is 64 bits, and F(30) = 832040 is tiny compared to its range. For much larger n the sum would eventually overflow, which stops the program in Swift instead of wrapping.

    Complexity

    Time: exponential. Every call with n of 2 or more makes two more calls, and they recompute the same values again and again. fibonacci(4) evaluates fibonacci(2) twice, and for larger n the repetition snowballs. Computing F(10) takes 177 calls, and F(30) takes 2,692,537. The count grows by about 1.6 times for each step in n, roughly O(1.618^n). That is acceptable for the limit of 30, but not much beyond it.

    Space: O(n). The calls form a chain at most n frames deep on the call stack. The two branches at each level are evaluated one after the other, not together.

    The repeated work can be removed by remembering results already computed, or by building the sequence from the bottom up with a loop. This lesson practises the plain recursion.

    Edge cases and common mistakes

    • n = 0 and n = 1. Both return n, giving 0 and 1.
    • Checking only n == 0. Then fibonacci(1) would call fibonacci(0) and fibonacci(-1), and the recursion would never end for any input.
    • Returning 1 for the base case. That gives F(0) = 1, which shifts the whole sequence.
    • Calling with the same n. A call like fibonacci(n) inside the function never gets smaller.
    • Forgetting the second call. fibonacci(n - 1) + fibonacci(n - 1) gives powers of two, not Fibonacci numbers.

    Testing

    • n = 0 gives 0.
    • n = 1 gives 1.
    • n = 2 gives 1.
    • n = 4 gives 3.
    • n = 10 gives 55.
    • n = 30 gives 832040.
    Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free