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

1) Print fibonacci series in reverse order using recursion in java 2) Print fibonacci series in reverse order using recursion in c++ 3) Print fibonacci series in reverse order using recursion in c 4) Print fibonacci series in reverse order using recursion in c# 5) Print fibonacci series in reverse order using recursion in vb.net 6) Print fibonacci series in reverse order using recursion in php 7) Print fibonacci series in reverse order using recursion in node js 8) Print fibonacci series in reverse order using recursion in typescript 9) Print fibonacci series in reverse order using recursion in python 10) Print fibonacci series in reverse order using recursion in ruby 11) Print fibonacci series in reverse order using recursion in scala 12) Print fibonacci series in reverse order using recursion in swift 13) Print fibonacci series in reverse order using recursion in kotlin 14) Print fibonacci series in reverse order using recursion in golang

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.