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.
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