In this tutorial, we will learn how to generate the Nth Fibonacci number using recursion in Swift. We will understand the Fibonacci sequence, write an algorithm for the solution, and implement it step by step with a complete Swift program and output.

What is the Fibonacci Sequence?

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. The sequence is defined as:

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

For example, the first few Fibonacci numbers are:

  • 0, 1, 1, 2, 3, 5, 8, 13, 21, …

We will now write a recursive algorithm to calculate the Nth Fibonacci number.

Algorithm to Calculate Nth Fibonacci Number

  1. Define a recursive function fibonacci that takes n as input.
  2. Base Case:
    1. If n == 0, return 0.
    2. If n == 1, return 1.
  3. Recursive Case: Return the sum of fibonacci(n-1) and fibonacci(n-2).

This algorithm uses recursion to break down the problem into smaller subproblems until it reaches the base cases.

Step-by-Step Implementation in Swift

1. Handle Base Cases

Define the base cases for the recursive function to handle n = 0 and n = 1:

</>
Copy
func fibonacci(_ n: Int) -> Int {
    if n == 0 {
        return 0 // Base case for F(0)
    } else if n == 1 {
        return 1 // Base case for F(1)
    }
    return 0 // Placeholder for recursive case
}

2. Add the Recursive Case

Implement the recursive logic to calculate fibonacci(n-1) and fibonacci(n-2):

</>
Copy
func fibonacci(_ n: Int) -> Int {
    if n == 0 {
        return 0 // Base case for F(0)
    } else if n == 1 {
        return 1 // Base case for F(1)
    }
    return fibonacci(n - 1) + fibonacci(n - 2) // Recursive case
}

Explanation:

  • fibonacci(_ n: Int): Defines a recursive function to calculate the Nth Fibonacci number.
  • if n == 0: Returns 0 for the base case F(0).
  • if n == 1: Returns 1 for the base case F(1).
  • fibonacci(n - 1) + fibonacci(n - 2): Calculates the Fibonacci number recursively by summing the two preceding Fibonacci numbers.

3. Test the Function

Let’s test the function with some example inputs:

</>
Copy
// Test cases
print("Fibonacci of 0: \(fibonacci(0))")  // Output: 0
print("Fibonacci of 1: \(fibonacci(1))")  // Output: 1
print("Fibonacci of 5: \(fibonacci(5))")  // Output: 5
print("Fibonacci of 7: \(fibonacci(7))")  // Output: 13

Complete Swift Program

Here’s the complete Swift program to generate the Nth Fibonacci number using recursion:

main.swift

</>
Copy
import Foundation

// Function to calculate the Nth Fibonacci number using recursion
func fibonacci(_ n: Int) -> Int {
    if n == 0 {
        return 0 // Base case for F(0)
    } else if n == 1 {
        return 1 // Base case for F(1)
    }
    return fibonacci(n - 1) + fibonacci(n - 2) // Recursive case
}

// Test cases
print("Fibonacci of 0: \(fibonacci(0))")  // Output: 0
print("Fibonacci of 1: \(fibonacci(1))")  // Output: 1
print("Fibonacci of 5: \(fibonacci(5))")  // Output: 5
print("Fibonacci of 7: \(fibonacci(7))")  // Output: 13

Output:

Fibonacci of 0: 0
Fibonacci of 1: 1
Fibonacci of 5: 5
Fibonacci of 7: 13
Program ended with exit code: 0

Xcode Screenshot

Swift Program to Generate Nth Fibonacci Number using Recursion