Fibonacci Using Recursion in DSA Python - Build from Scratch

Fibonacci Using Recursion

📖 Scenario: You want to find numbers in the famous Fibonacci sequence. This sequence starts with 0 and 1, and each next number is the sum of the two before it. You will write a small program that uses a simple repeating process called recursion to find Fibonacci numbers.

🎯 Goal: Build a Python program that uses a recursive function to find the Fibonacci number at a given position.

📋 What You'll Learn

Create a recursive function named fibonacci that takes one number n.

Use base cases to return 0 when n is 0 and 1 when n is 1.

Use recursion to return the sum of fibonacci(n-1) and fibonacci(n-2) for other values.

Create a variable position to store the Fibonacci position to find.

Print the Fibonacci number at the given position.

💡 Why This Matters

🌍 Real World

Fibonacci numbers appear in nature, computer algorithms, and financial models. Understanding recursion helps solve many problems that break down into smaller similar problems.

💼 Career

Knowing recursion and Fibonacci sequence is a common interview topic for programming jobs. It shows your ability to think recursively and write clean code.

1

Create the Fibonacci function base

Define a function called fibonacci that takes one parameter n. Inside the function, write two base cases: return 0 if n == 0, and return 1 if n == 1.

DSA Python

# Define fibonacci function with base cases
# Your code here

Hint

Think of the first two Fibonacci numbers as special cases. Use if statements to return them directly.

2

Add the recursive call to Fibonacci function

Inside the fibonacci function, after the base cases, add a return statement that returns the sum of fibonacci(n - 1) and fibonacci(n - 2).

DSA Python

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    # Add recursive return statement here
    # Your code here

Hint

Use the function itself to find the two previous Fibonacci numbers and add them.

3

Create the position variable

Create a variable called position and set it to 7. This will be the position in the Fibonacci sequence you want to find.

DSA Python

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

# Create position variable
# Your code here

Hint

Just create a variable named position and assign the number 7 to it.

4

Print the Fibonacci number at the position

Use print to display the result of calling fibonacci(position).

DSA Python

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

position = 7

# Print the Fibonacci number at position
# Your code here

Hint

Call the fibonacci function with position and print the result.

Practice

1. What does the Fibonacci sequence represent when calculated using recursion?

easy

A. Each number is the square of the previous number

B. Each number is the product of the two preceding numbers

C. Each number is the difference of the two preceding numbers

D. Each number is the sum of the two preceding numbers

Solution

1. Step 1: Understand Fibonacci sequence definition

   The Fibonacci sequence is defined such that each number is the sum of the two numbers before it.

2. Step 2: Relate to recursion

   Recursion calculates this by calling the function for the two previous numbers and adding their results.

3. Final Answer:

   Each number is the sum of the two preceding numbers -> Option D

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds two previous numbers, not multiply or subtract [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing difference with sum
• Assuming Fibonacci squares previous number

2. Which of the following is the correct base case syntax for a recursive Fibonacci function in Python?

easy

A. if n == 0 or n == 1: return n

B. if n < 0: return 0

C. if n == 2: return 1

D. if n == 1: return 0

Solution

1. Step 1: Identify base cases for Fibonacci

   Fibonacci sequence starts with 0 at position 0 and 1 at position 1, so base cases are n == 0 and n == 1.

2. Step 2: Check syntax correctness

   The correct syntax returns n when n is 0 or 1, matching the base cases.

3. Final Answer:

   if n == 0 or n == 1: return n -> Option A

4. Quick Check:

   Base cases return n for 0 or 1 [OK]

Hint: Base cases return n when n is 0 or 1 [OK]

Common Mistakes:

• Using wrong base case values
• Returning 0 for n == 1
• Missing base case for n == 0

3. What is the output of the following code?

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

print(fib(4))

medium

A. 4

B. 5

C. 3

D. 7

Solution

1. Step 1: Trace fib(4) calls

   fib(4) = fib(3) + fib(2); fib(3) = fib(2) + fib(1); fib(2) = fib(1) + fib(0)

2. Step 2: Calculate values bottom-up

   fib(0)=0, fib(1)=1; fib(2)=1+0=1; fib(3)=1+1=2; fib(4)=2+1=3

3. Final Answer:

   3 -> Option C

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Calculate fib(n-1) + fib(n-2) stepwise [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Adding wrong values for fib(2) or fib(3)
• Forgetting base cases

4. Find the error in this recursive Fibonacci function:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) - fib(n-2)

medium

A. The base cases are incorrect

B. The recursive step uses subtraction instead of addition

C. The function lacks a return statement

D. The function will cause infinite recursion

Solution

1. Step 1: Check base cases

   Base cases for n == 0 and n == 1 are correct and return proper values.

2. Step 2: Analyze recursive step

   The recursive step uses subtraction (fib(n-1) - fib(n-2)) instead of addition, which is incorrect for Fibonacci.

3. Final Answer:

   The recursive step uses subtraction instead of addition -> Option B

4. Quick Check:

   Recursive step must add previous two values [OK]

Hint: Fibonacci recursion adds, never subtracts previous two [OK]

Common Mistakes:

• Using subtraction in recursive step
• Misunderstanding base cases
• Missing return keyword

5. How many total calls are made when computing fib(5) using the naive recursive Fibonacci function?

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n-1) + fib(n-2)

hard

A. 15

B. 9

C. 7

D. 10

Solution

1. Step 1: Count calls for fib(5)

   fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) and fib(2); fib(3) calls fib(2) and fib(1), etc.

2. Step 2: Calculate total calls

   Total calls = 15 (including repeated calls for fib(3), fib(2), fib(1), fib(0)) as the recursion tree expands.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Naive recursion calls grow exponentially; fib(5) = 15 calls [OK]

Hint: Count all calls in recursion tree for fib(n) [OK]

Common Mistakes:

• Counting only unique calls
• Ignoring repeated calls in recursion
• Underestimating exponential growth