Generate Fibonacci Using Recursion

Generate Fibonacci Using Recursion

Hard C++ Functions 43 views
Explanation Complexity

Problem Statement

Generate nth Fibonacci number recursively.
Real Life: Understanding recursive patterns in nature.

Input Format

An integer N (position in Fibonacci sequence).

Output Format

Nth Fibonacci number.

Example

6
8

Constraints

• N ≥ 0

• Recursive method

• Large N is slow with recursion

Concept Explanation

Fibonacci sequence is defined as:

• F(0) = 0

• F(1) = 1

• F(N) = F(N-1) + F(N-2)

Each number is formed using the previous two numbers.

Step-by-Step Explanation

1.If N == 0, return 0 (base case).

2.If N == 1, return 1 (base case).

3.Otherwise:

• Call function for N-1.

• Call function for N-2.

4.Add both returned values.

5.Return the sum as the nth Fibonacci number.

Concept Explanation

Fibonacci sequence is defined as:

• F(0) = 0

• F(1) = 1

• F(N) = F(N-1) + F(N-2)

Each number is formed using the previous two numbers.

Step-by-Step Explanation

1.If N == 0, return 0 (base case).

2.If N == 1, return 1 (base case).

3.Otherwise:

• Call function for N-1.

• Call function for N-2.

4.Add both returned values.

5.Return the sum as the nth Fibonacci number.

Input / Output Format

Input Format
An integer N (position in Fibonacci sequence).
Output Format
Nth Fibonacci number.
Constraints
• N ≥ 0

• Recursive method

• Large N is slow with recursion

Examples

Input:
6
Output:
8

Example Solution (Public)

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

void function_q12_fibonacci_recursion() {
    int term = 8;
    cout << "Fibonacci series: ";
    for(int i = 0; i < term; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
}

Official Solution Code

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

void function_q12_fibonacci_recursion() {
    int term = 8;
    cout << "Fibonacci series: ";
    for(int i = 0; i < term; i++) {
        cout << fibonacci(i) << " ";
    }
    cout << endl;
}
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.