Posted on by Kalkicode
Code Recursion

Fibonacci series in reverse order

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. The Fibonacci series is a classic mathematical concept that has many applications in various fields, including computer science and algorithms.

In this context, we are interested in generating the Fibonacci series in reverse order using a recursive algorithm. Given a positive integer n, we want to find the last n Fibonacci numbers in reverse order.

Explanation using Example

Let's consider the two test cases from the provided code:

Test A: n = 10

The first 10 Fibonacci numbers are [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]. When displayed in reverse order, they become [34, 21, 13, 8, 5, 3, 2, 1, 1, 0], which is the expected output.

Test B: n = 15

The first 15 Fibonacci numbers are [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]. When displayed in reverse order, they become [377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 0], which is the expected output.

Pseudocode

fibonacciNumber(a, b, n)
    if n <= 0
        return
    fibonacciNumber(b, a + b, n - 1)
    print a

Algorithm Explanation

The fibonacciNumber function is a recursive algorithm to generate the last n Fibonacci numbers in reverse order. It takes three parameters: a, b, and n. The variables a and b represent the two preceding Fibonacci numbers, and n represents the count of remaining Fibonacci numbers to be generated.

The algorithm starts by checking if n is less than or equal to 0. If n is non-positive, it returns, as there are no more Fibonacci numbers to generate.

Next, it recursively calls fibonacciNumber with the parameters b and a + b (the next Fibonacci number), and decrements n by 1. This step ensures that the algorithm generates the Fibonacci numbers in reverse order.

Finally, the algorithm prints the current value of a, which represents the next Fibonacci number in reverse order.

Program List

Time Complexity

The time complexity of the provided algorithm is O(n), where n is the number of Fibonacci numbers to generate. This is because the algorithm makes n recursive calls, and each call takes constant time to compute the next Fibonacci number and print it. Hence, the overall time complexity is linear with respect to the input n.

Resultant Output Explanation

For Test A with n = 10, the algorithm generates the last 10 Fibonacci numbers in reverse order, and the output is [34, 21, 13, 8, 5, 3, 2, 1, 1, 0], which matches the expected result.

For Test B with n = 15, the algorithm generates the last 15 Fibonacci numbers in reverse order, and the output is [377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 0], which also matches the expected result.

The code successfully generates the Fibonacci series in reverse order using recursion for the given test cases.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment