473,320 Members | 1,965 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Converting a function to non-recursive

Im supposed to create a recursive and non recursive function to calculate this.
F(n) = 1 for n = 0 or n = 1 or n=2
F(n) = F((n+1)/2)^2 + F((n-1)/2)^ 2 for n is odd
F(n) = F(n/2 + 1)^2 – F(n/2 – 1)^ 2 for n is even
I know how to do the recursive one which looks like this and returns the fibonacci numbers
if (n == 0 || n == 1 || n == 2) {
return 1;}
else if (n % 2 == 0) {
a=F(n/2+1);
b=F(n/2-1);
return a*a - b*b; }
else {
c=F((n+1)/2);
d=F((n-1)/2);
return c*c + d*d; }
but how do you change it to a non-recursive function?
Jul 1 '07 #1
1 2359
First of all, F(0) should return 0 not 1, either that, or F(2) should be 2.

Anyways, to make it non-recursive you need to abandon the given formula because it only works recursively. Instead your function should keep 3 integer variables, lets say: int first = 0, int second = 1, and answer = 0.

Check if n = 0 or 1, and return the correct value otherwise you put a for loop that loops n - 1 times. In the loop add first and second and store it in temp, then set first equal to second and second equal to temp. Then after to loop you return answer.

If you are right, and 0, 1, and 2 are all supposed to return 1, then initialize answer to 1 instead of 0. But if that's the case then it's not a real fab number, since F(2) should equal F(0) + F(1), which is either 0 + 1 = 1, or 1 + 1 = 2.

I didn't give you any actual code, you should be able to figure that out from this algorithm.

NOTE: because of the limits of int (32) you can only accurately calculate up to the 46th fab number, because after that it overflows into the negative end of the spectrum, which then starts giving erroneous results.
Jul 1 '07 #2

Sign in to post your reply or Sign up for a free account.

Similar topics

2
by: Asbjørn Ulsberg | last post by:
Hi. I'm trying to convert Brady Hegberg's great RTF2HTML VB 6.0 module to C#. I've managed to convert the VB code to VB.NET, which gave me the following code: Option Strict On Option...
4
by: mabosch | last post by:
I'm trying to convert a DOC to JPG it works in Windows Forms, but I run under asp.net the clipboard its empty, I'm doing Dim objWord As New Word.Application Dim objDoc As Word.Document Const...
36
by: kjvt | last post by:
Based on a prior posting, I've written a function to convert a recordset to a dataview. The first call to the function for a given recordset works perfectly, but the second call always returns a...
23
by: Nikhil Patel | last post by:
Hi all, How can I convert an integer to its equivalent ascii character without using Microsoft.VisualBasic dll or any other dll(I want to reference only System.dll). Thanks. -Nikhil
3
by: Parvesh | last post by:
hi, I am using a webservice which Returns the Result in an XML string, The XML response i get i svery cumbersome to parse, But if i could convert it to the Corresponding Class using the...
9
by: Terry | last post by:
I am converting (attempting) some vb6 code that makes vast use of interfaces. One of the major uses is to be able to split out Read-only access to an obect. Let me give you a simple (contrived)...
2
by: Alex Buell | last post by:
Is there an elegant way of converting strings containing digits between different number bases in C++? I.e.: 10 (base 2) = 2 (base 10) FF (base 16) = 256 (base 10) F (base 16) = 1111 (base 2)...
116
by: Dilip | last post by:
Recently in our code, I ran into a situation where were stuffing a float inside a double. The precision was extended automatically because of that. To make a long story short, this caused...
107
by: bmshivaraj | last post by:
Hi, Could any one tell me how to convert a unsigned long value into string (char *) ? In C++ there is a function _ultoa so wanted a similar one in C . Regards, Shivaraj
35
by: Sean Farrow | last post by:
Hi: What is best and safest way of converting a char* to a const char *? Can I use const_cast? Cheers Sean.
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.