Fibonacci Using Recursion in DSA Java - Build from Scratch

Fibonacci Using Recursion

📖 Scenario: You are helping a friend understand how to calculate Fibonacci numbers using a simple method that calls itself. Fibonacci numbers are a famous sequence where each number is the sum of the two before it, starting with 0 and 1.

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

📋 What You'll Learn

Create a method called fibonacci that takes an integer n and returns the Fibonacci number at position n.

Use recursion inside the fibonacci method to calculate the result.

Call the fibonacci method for the number 7 and store the result in a variable called result.

Print the value of result.

💡 Why This Matters

🌍 Real World

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

💼 Career

Recursion is a key concept in programming interviews and algorithm design. Knowing how to implement Fibonacci recursively shows understanding of function calls and problem decomposition.

1

Create the Fibonacci method signature

Write a public static method called fibonacci that takes an integer parameter n and returns an integer.

DSA Java

public class FibonacciRecursion {

    // Define the fibonacci method here
    // Your code here
}

Hint

Start by writing the method header with the correct name, parameter, and return type.

2

Add base cases for recursion

Inside the fibonacci method, add two base cases: if n is 0, return 0; if n is 1, return 1.

DSA Java

public class FibonacciRecursion {

    public static int fibonacci(int n) {
        // Add base cases for n == 0 and n == 1
        // Your code here
    }

}

Hint

Base cases stop the recursion. Return 0 for 0 and 1 for 1.

3

Add recursive calls to calculate Fibonacci

In the fibonacci method, after the base cases, return the sum of fibonacci(n - 1) and fibonacci(n - 2).

DSA Java

public class FibonacciRecursion {

    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        // Return fibonacci(n - 1) + fibonacci(n - 2)
        // Your code here
    }

}

Hint

Use the method itself to get the two previous Fibonacci numbers and add them.

4

Call the method and print the result

In the main method, call fibonacci(7), store the result in an integer variable called result, and print result.

DSA Java

public class FibonacciRecursion {

    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        // Call fibonacci(7), store in result, and print result
        // Your code here
    }
}

Hint

Remember to create the main method, call fibonacci(7), save it in result, and print it.

Practice

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

easy

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

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

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

D. Each number is the square of the previous number

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 calls the function for the two previous numbers and adds their results to get the current number.

3. Final Answer:

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

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds two previous numbers to get next [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 Java?

easy

A. if (n == 0 || n == 1) return n;

B. if (n == 0 && n == 1) return n;

C. if (n = 0 || n = 1) return n;

D. if (n != 0 || n != 1) return n;

Solution

1. Step 1: Identify correct base case condition

   The base case must check if n is 0 or 1 using '==' for comparison and logical OR '||'.

2. Step 2: Check syntax correctness

   if (n == 0 || n == 1) return n; uses correct comparison operators and logical OR. Others use incorrect operators or logic.

3. Final Answer:

   if (n == 0 || n == 1) return n; -> Option A

4. Quick Check:

   Base case uses '==' and '||' [OK]

Hint: Use '==' for comparison and '||' for OR in base case [OK]

Common Mistakes:

• Using '=' instead of '==' for comparison
• Using '&&' instead of '||' in base case
• Incorrect negation or logic in condition

3. What is the output of the following Java code?

public class FibTest {
  public static int fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n - 1) + fib(n - 2);
  }
  public static void main(String[] args) {
    System.out.println(fib(4));
  }
}

medium

A. 7

B. 5

C. 4

D. 3

Solution

1. Step 1: Calculate fib(4) using recursion

   fib(4) = fib(3) + fib(2) - fib(3) = fib(2) + fib(1) = (fib(1) + fib(0)) + 1 = (1 + 0) + 1 = 2 - fib(2) = fib(1) + fib(0) = 1 + 0 = 1 So fib(4) = 2 + 1 = 3

2. Step 2: Confirm output printed

   The main method prints fib(4), which is 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Calculate fib(n) by adding fib(n-1) and fib(n-2) [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Miscomputing base cases
• Adding wrong recursive results

4. Identify the error in this recursive Fibonacci function and select the fix:

public static int fib(int n) {
  if (n == 0 || n == 1) {
    return 0;
  }
  return fib(n - 1) + fib(n - 2);
}

medium

A. Change 'return 0;' to 'return n;' in base case

B. Change 'if' condition to 'n == 2 || n == 3'

C. Add a loop inside the function

D. Remove the base case entirely

Solution

1. Step 1: Analyze base case return value

   The base case returns 0 for both n=0 and n=1, but fib(1) should return 1.

2. Step 2: Correct base case return

   Return n for base cases 0 and 1 to correctly represent Fibonacci values.

3. Final Answer:

   Change 'return 0;' to 'return n;' in base case -> Option A

4. Quick Check:

   Base case returns n for n=0 or 1 [OK]

Hint: Base case must return n, not always 0 [OK]

Common Mistakes:

• Returning 0 for fib(1)
• Changing base case condition incorrectly
• Removing base case causing infinite recursion

5. You want to find the 6th Fibonacci number using recursion but want to avoid repeated calculations. Which technique can you apply to optimize the recursive Fibonacci function?

hard

A. Increase the base case to n == 5

B. Replace recursion with an infinite loop

C. Use memoization to store and reuse computed results

D. Use a global variable to count calls

Solution

1. Step 1: Understand recursion inefficiency

   Recursive Fibonacci recalculates the same values many times, causing slow performance.

2. Step 2: Apply memoization

   Memoization stores results of fib(n) in a cache so repeated calls return cached values, improving speed.

3. Final Answer:

   Use memoization to store and reuse computed results -> Option C

4. Quick Check:

   Memoization avoids repeated calculations [OK]

Hint: Cache results to avoid repeated recursive calls [OK]

Common Mistakes:

• Changing base case incorrectly
• Using infinite loops causing crashes
• Counting calls without optimization