All Questions
Tagged with recursive-algorithms fibonacci-numbers
21
questions
3
votes
1
answer
327
views
Time complexity of computing Fibonacci numbers using naive recursion
I'm trying to rigorously solve the Time Complexity $T(n)$ of the naive (no memoization) recursive algorithm that computes the Fibonacci numbers.
In other words I'm looking for $f(n):T(n)\in\Theta(f(n))...
- 342
0
votes
0
answers
32
views
Trying to figure out to solve the below Fibonacci Sequence, need to validate with the results I have got
Define the New Fibonacci sequence (denoted NF) to have the same
recursive definition for n greater or equal than 2 as the Fibonacci
sequence, except where the base cases are now changed to NF0 equals ...
- 1
0
votes
1
answer
885
views
How many repeated steps in a Fibonacci recursive function [closed]
how can i calculate how many repeated calls occur in a fib recursive function.
fib(n):
if n = 0 : ret 0
if n = 1 : ret 1
ret fib(n - 1) + fib(n - 2)
ex) if n = 5 how many times fib(...
- 103
0
votes
1
answer
574
views
Recursion: How many additions are needed to calculate the n-th Fibonacci number?
If the Fibonacci numbers are given by $F_n = F_{n-1} + F_{n-2}$, find and solve a recursion for the amount of additions needed to calculate the n-th Fibonacci number.
I think i've figured out the ...
2
votes
1
answer
165
views
A little help for building the Fibonacci spiral in a particular reference system
In the following picture, the numbers represent the building steps of the Fibonacci spiral (or Golden spiral).
I would like to find the coordinates of the upper-left corner of the squares (black dots)...
user559615
0
votes
0
answers
62
views
Stuck Simplifying for a Fibonacci Series
I am attempting to solve for $n$ in the equation:
$g_n=g_1F_{n-1}+g_2F_n$
where $F_n$ is the $n$th Fibonacci number. I know that $g_0$ and $g_1$ will be positive integers such that $0 < g_1 \leq ...
- 149
2
votes
2
answers
581
views
Fibonacci Calls
The ’fib’ function returns the $n^{th}$
Fibonacci number if called using ’$fib(n)$’
Suppose calling ’$fib(n)$’ requires G(n)
calls to the ’fib’ function in total, because of recursion Prove that
$G(n) ...
- 121
1
vote
3
answers
90
views
Given an integer $n$ find the smallest index $k$ such that $\text{fib}(k) \ge n$ in logarithmic time? [closed]
Given an integer $n$ find the smallest index $k$ such that $\text{fib}(k) \ge n$ in logarithmic time?
I've already programmed several algorithms to compute the $i$'th Fibonacci number $\text{fib}(i)$ ...
- 5,653
1
vote
2
answers
3k
views
derivation of fibonacci log(n) time sequence
I was trying to derive following equation to compute the nth fibonacci number in O(log(n)) time.
F(2n) = (2*F(n-1) + F(n)) * F(n)
which i found on wiki form the ...
- 121
4
votes
2
answers
160
views
Fibonacci recursive algorithm yields interesting result
After writing a program in Java to generate Fibonacci numbers using a recursive algorithm, I noticed the time increase in each iteration is approximately $\Phi$ times greater than the previous.
$\Phi$...
- 143
7
votes
1
answer
3k
views
How many distinct ways to climb stairs in 1 or 2 steps at a time? (Fibonacci puzzle)
There is a very interesting puzzle for Fibonacci sequence:
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb $1$ or $2$ steps. In how many distinct ...
- 173
1
vote
1
answer
63
views
Number of strings of size $k$ that do not have 'ab'
Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab'
Find strings, of size $k$ is in $L$ ($L_k$)
Consider $A_k$ (strings of size $k$ that end in $a$) ...
- 413
4
votes
2
answers
128
views
Fibonaaci Recurrence
This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities
Given Data in question
$F_n=F_{n-1}+...
- 1,717
1
vote
3
answers
80
views
Relation between series and equations
There is following quotes from wiki on Plastic number:
The powers of the plastic number $A(n) = ρ^n$ satisfy the recurrence relation $A(n) = A(n − 2) + A(n − 3)$ for $n > 2$.
And 2nd is that
...
- 267
6
votes
5
answers
8k
views
Where do the first two numbers of Fibonacci Sequence come from? [duplicate]
I'm trying to code a simple algorithm that prints out the $n^{th}$ Fibonacci number. However, my program requires the initial seed values $F_0 = 0$ and $F_1 = 1$, when I'm hopeful I can figure ...
- 1,855