Fibonacci Using Recursion in DSA Typescript - Build from Scratch

Fibonacci Using Recursion

📖 Scenario: You want to calculate the Fibonacci number at a certain position. The Fibonacci sequence starts with 0 and 1, and each next number is the sum of the two before it.Imagine you are building a simple calculator that finds the Fibonacci number for a given position using a method called recursion, where the function calls itself.

🎯 Goal: Build a recursive function called fibonacci that takes a number n and returns the Fibonacci number at position n.Then, use this function to find the Fibonacci number at position 6 and print the result.

📋 What You'll Learn

Create a variable n with the value 6.

Create a recursive function called fibonacci that takes a number num and returns the Fibonacci number at that position.

Use the base cases: if num is 0, return 0; if num is 1, return 1.

For other cases, return the sum of fibonacci(num - 1) and fibonacci(num - 2).

Call the fibonacci function with n 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 write and understand recursive functions is important for software development roles.

1

Create the input variable

Create a variable called n and set it to the number 6.

DSA Typescript

# Your code here

Hint

Use const n = 6; to create the variable.

2

Write the recursive Fibonacci function

Create a function called fibonacci that takes a parameter num of type number. Inside the function, write these rules:
- If num is 0, return 0.
- If num is 1, return 1.
- Otherwise, return fibonacci(num - 1) + fibonacci(num - 2).

DSA Typescript

const n = 6;
// Your code here

Hint

Use function fibonacci(num: number): number { ... } and the base cases with if statements.

3

Call the function and store the result

Call the fibonacci function with the variable n and store the returned value in a variable called result.

DSA Typescript

const n = 6;

function fibonacci(num: number): number {
    if (num === 0) {
        return 0;
    }
    if (num === 1) {
        return 1;
    }
    return fibonacci(num - 1) + fibonacci(num - 2);
}

// Your code here

Hint

Use const result = fibonacci(n); to call the function and save the answer.

4

Print the Fibonacci result

Print the value of the variable result using console.log.

DSA Typescript

const n = 6;

function fibonacci(num: number): number {
    if (num === 0) {
        return 0;
    }
    if (num === 1) {
        return 1;
    }
    return fibonacci(num - 1) + fibonacci(num - 2);
}

const result = fibonacci(n);

// Your code here

Hint

Use console.log(result); to show the answer.

Practice

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

easy

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

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 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: Recognize recursion use

   Recursion calls the function itself to calculate previous two numbers and sums them.

3. Final Answer:

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

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

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

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing subtraction or squares with addition
• Assuming Fibonacci is a product sequence

2. Which of the following is the correct TypeScript function signature for a recursive Fibonacci function?

easy

A. function fib(n: string): string

B. function fib(n: boolean): boolean

C. function fib(n: number): number

D. function fib(): void

Solution

1. Step 1: Identify input and output types

   The Fibonacci function takes a number input and returns a number output.

2. Step 2: Match correct function signature

   Only the signature with number input and number output matches the Fibonacci function requirements.

3. Final Answer:

   function fib(n: number): number -> Option C

4. Quick Check:

   Input and output types must be number [OK]

Hint: Fibonacci input/output are numbers, not strings or booleans [OK]

Common Mistakes:

• Using wrong parameter types like string or boolean
• Missing return type or using void
• Confusing function signature syntax

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

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
console.log(fib(4));

medium

A. 5

B. 7

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

   The console.log prints 5 as the result of fib(4).

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(4) = 5 [OK]

Hint: Trace fib calls step-by-step to sum previous two results [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Miscounting base cases fib(0) and fib(1)
• Adding wrong recursive results

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

function fib(n: number): number {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n - 1) - fib(n - 2);
}

medium

A. Change base case n == 0 to n <= 0

B. Change subtraction to addition in return statement

C. Remove base cases completely

D. Change function to return string instead of number

Solution

1. Step 1: Analyze return statement

   The function uses subtraction (fib(n - 1) - fib(n - 2)) which is incorrect for Fibonacci.

2. Step 2: Correct the operation

   Fibonacci requires addition of previous two numbers, so change '-' to '+'.

3. Final Answer:

   Change subtraction to addition in return statement -> Option B

4. Quick Check:

   Fibonacci sums previous two numbers [OK]

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

Common Mistakes:

• Using subtraction instead of addition
• Removing base cases causing infinite recursion
• Changing return type unnecessarily

5. Given the recursive Fibonacci function below, what is the output of fib(0) and fib(1)? Why are these base cases important?

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

hard

A. fib(0) = 0, fib(1) = 1; base cases are optional

B. fib(0) = 1, fib(1) = 0; base cases speed up recursion

C. fib(0) = 1, fib(1) = 1; base cases prevent wrong output

D. fib(0) = 0, fib(1) = 1; base cases stop infinite recursion

Solution

1. Step 1: Evaluate base cases fib(0) and fib(1)

   fib(0) returns 0 and fib(1) returns 1 as per the condition n <= 1 returns n.

2. Step 2: Understand importance of base cases

   Base cases stop the recursion from continuing infinitely by providing direct answers for smallest inputs.

3. Final Answer:

   fib(0) = 0, fib(1) = 1; base cases stop infinite recursion -> Option D

4. Quick Check:

   Base cases return 0 and 1 to end recursion [OK]

Hint: Base cases return n for n ≤ 1 to stop recursion [OK]

Common Mistakes:

• Mixing up fib(0) and fib(1) values
• Thinking base cases are optional
• Ignoring recursion stopping condition