Start learning free

LESSON 284 OF 414 · RECURSION

Recursive Fibonacci in Rust: Base Case and Two Calls

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

    RUST · RECURSION

    Recursive Fibonacci in Rust, explained

    Problem overview

    The function fibonacci takes an i32, n, and returns the n-th Fibonacci number. The sequence starts with F(0) = 0 and F(1) = 1, and every later number is the sum of the two before it: F(n) = F(n - 1) + F(n - 2). The input is between 0 and 30.

    For n = 4 the answer is 3, because F(4) = F(3) + F(2) = 2 + 1. The first values are 0, 1, 1, 2, 3, 5, 8, 13, and fibonacci(10) is 55.

    Approach: the definition is already a recursive function

    A recursive function solves a problem by calling itself on smaller versions of the same problem. The Fibonacci definition has exactly that shape. To get F(n), you need F(n - 1) and F(n - 2), and each of those needs two smaller values, and so on.

    Every recursive function needs two parts:

    • A base case that returns an answer directly, without another call. Without it, the calls never stop.
    • A recursive case that moves toward the base case. Here n - 1 and n - 2 are both smaller than n, so each chain of calls ends at 0 or 1.

    The two starting values F(0) = 0 and F(1) = 1 have a convenient property: in both cases the answer equals n. One check, n < 2, covers both.

    Step by step

    1. Write the base case first. If n is less than 2, return n. This is an early exit from the middle of the function, so it uses the return keyword.
    2. Write the recursive case last. For any other n, add the results of the two smaller calls. This sum is the last expression of the function, with no return and no semicolon, so it becomes the return value.

    Inside an impl block, a function that takes no self is called as Self::fibonacci(...), not as a bare fibonacci(...).

    The solution in Rust

    impl Solution {
    fn fibonacci(n: i32) -> i32 {
        if n < 2 {
            return n;
        }
        Self::fibonacci(n - 1) + Self::fibonacci(n - 2)
    }
}

    The Rust details worth a closer look:

    • The last expression is the result. A line without a trailing semicolon is an expression, and the final one in a function body is what the function returns. Writing Self::fibonacci(n - 1) + Self::fibonacci(n - 2); with a semicolon would turn it into a statement, the function would return () instead of an i32, and the compiler would reject it with a type mismatch.
    • return is for early exits. The base case needs it because more code follows. At the end of the function the plain expression is the idiomatic form.
    • Rust never converts between integer types silently. n is an i32 and so is the result, so no casts are needed. The sum could overflow an i32 for large n, but for 0 to 30 the biggest value, F(30), is 832040.
    • Recursion uses the call stack. The depth here is at most n, which is tiny for 30.

    Complexity

    Time: exponential. Each call with n >= 2 makes two more calls, and the same subproblems are solved again and again. For example, F(2) is computed from scratch inside both F(3) and F(4). Counting the calls gives 21891 for fibonacci(20) and 2692537 for fibonacci(30). The count grows by a factor of about 1.6 with each step of n, roughly O(1.6^n). That is fine for n up to 30, and the statement says not to worry about it. Storing results that were already computed, or looping from the bottom up, brings it down to O(n).

    Space: O(n). Only one chain of calls is active at a time, and the longest chain follows n - 1 repeatedly down to 1, so at most about n calls are on the stack.

    Edge cases and common mistakes

    • Missing base case. Without the n < 2 check, the calls continue through 0, -1, -2 and never stop, until the stack overflows and the program aborts.
    • Checking only n == 0. A base case for 0 alone leaves F(1) calling F(0) and F(-1), and the recursion runs away. Both 0 and 1 need to stop.
    • Returning 1 for small inputs. F(0) is 0, so returning 1 for every n < 2 shifts the whole sequence.
    • Adding a semicolon to the last line. The function would no longer produce a value.
    • Forgetting Self::. Calling fibonacci(n - 1) inside the impl block fails to compile, because the function belongs to Solution.

    Testing

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