How do i calculate n-th fibonacci number recursively ? (using arrays)

Question

0.00/5 (No votes)

See more:

hi,

I need to write a program that computes the nth Fibonacci number using C++. The result (nth Fibonacci number) will be maximum 128bit and I have to use int arrays to solve the problem. I already did the part that computes the nth fibonacci number using arrays. I defined 3 arrays to solve the problem:

C++

// digits of a number are stored in array.
...
unsigned int fib1[100];
unsigned int fib2[100];
unsigned int result[101];
...

result is the summation of fib1 and fib2; for example [2,1] + [3,4] = [5,5] (21+34=55)

But now I need to write another program that computes the nth Fibonacci number recursively. I really don't know how to do that for 128bit numbers. Is there any way to reimplement my code to solve this problem?

Or anyone has another idea?

PS : I am not allowed to use "long double" type or any prepared library like TTmath or GMP.

Posted 28-Mar-11 14:36pm

dukenukem18

Updated 28-Mar-11 14:46pm

Henry Minute

v2

Add a Solution

2 solutions

Solution 2

It's even faster to write it on your own. Just follow the bare definition ~~and use the loop, no recursion~~. Oops! You say "recursive". OK then, use recursion.
Any type is fine, it does not really matter for the algorithm.

Instead of wasting time on finding exact implementation, use just first principles: http://en.wikipedia.org/wiki/Fibinochi_numbers[^] (I think you already know that, but take a look).
By the way, take this hint: you don't really need an array, unless you're required to return the array of 0..N Fibonacci numbers, not N-th Fibonacci number as you put it in first place.

If you have the implementation with long double, just change to type the 128-bit integer or any other at your liking: the algorithm should not change.

—SA

Posted 28-Mar-11 16:11pm

Sergey Alexandrovich Kryukov

Updated 28-Mar-11 16:24pm

v4

Comments

Аslam Iqbal 29-Mar-11 3:39am

good link

Sergey Alexandrovich Kryukov 29-Mar-11 10:39am

Thank you, Aslam.
A good way to get 1 from a lazy homeworkers...
--SA

dukenukem18 29-Mar-11 16:12pm

lazy homeworker ? i m trying OK ?? i'm not good at programming. i tried some ways to solve that and i already completed most of it. at the end, i just wrote here to take some advice to solve a part of my problem, and i was just looking for an advice NOT code or wikipedia link(!) !

Sergey Alexandrovich Kryukov 29-Mar-11 17:01pm

Aha, so you admit it was your vote of "1" by saying that?
I meant somebody who voted "1", anonymous person who cannot take any offense by definition, being anonymous.

Now, you're saying it's you. What am I supposed to to? Just to explain you this: You say "I'm not good at programming". It should mean you want to become a good one. There is only one way of becoming a such person: make your hands dirty and do the job. People spend a lot of their free time to give your real help.

You're not happy with NOT code?
It simple means you're not welcome here.

I will blacklist you.
And you're not going to be a developer unless you dramatically change your attitude.

Sorry,
--SA

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Henry Minute · Accepted Answer · 2011-03-28T14:48:00

Solution 1

If you do an internet search for c++ recursive fibonacci you will find lots of solutions.

Which would have been quicker than asking here!

Posted 28-Mar-11 14:48pm

Henry Minute

Comments

dukenukem18 28-Mar-11 21:09pm

hi , i already searched for it but most of them use common way (following code block) or "long double" type.

<pre>
int fib(int n)
{
if (n <= 2)
return 1
else
return fib(n-1) + fib(n-2)
}
</pre>

this is not what i'm looking for. i need to reimplement this code for 128bit numbers according to the conditions i already wrote in my question.

Sergey Alexandrovich Kryukov 29-Mar-11 10:40am

Good advice, Henry, my 5. Probably mine is even more radical... :-)
--SA

Sergey Alexandrovich Kryukov 29-Mar-11 17:03pm

Henry, please pay attentions for the OP's comment. It was explicitly told the reason of down-vote due to giving NOT CODE. This is more than enough for blacklisting. Such people should be banned.

--SA