Public Group

# Recursive functions - code critique?

This topic is 1967 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi!

I am just learning recursive functions so I was wondering if you can give me any advice - here's my code:

#include <iostream>
#include <vector>
using namespace std;

int GetFibNumber(int);
//Recursive function
void ArrayFib(int);
void PresentArray();
vector<int> FibArray;

int main()
{
int FibIndex = 0;
cout << "Enter an index for the Fibonacci number you want: ";
cin >> FibIndex;

cout << "Here's the number at that FibIndex: " << GetFibNumber(FibIndex) << endl;

cout << "Enter the index up to where you want the Fibonacci numbers: ";
cin >> FibIndex;
cout << "Here're the first " << FibIndex+1 << " Fibonacci numbers: " << endl;
ArrayFib(FibIndex);
PresentArray();

cin.sync();
cin.ignore();

return 0;
}

int GetFibNumber(int index)
{
if(index < 2)
return index;
else
return GetFibNumber(index-2) + GetFibNumber(index-1);
}

void ArrayFib(int index)
{
if(index == 0)
{
FibArray.push_back(0);
return;
}

if(index == 1)
{
FibArray.push_back(0);
FibArray.push_back(1);
return;
}

if(index >= 2)
{
//Recursivity
ArrayFib(index-1);
FibArray.push_back(FibArray[index-2]+FibArray[index-1]);
return;
}

}

void PresentArray()
{
for(int i = 0; i<FibArray.size()-1; i++)
{
cout << FibArray << ", ";
}

if(FibArray.size() >= 1)
cout << FibArray[FibArray.size()-1] << " The End!" << endl;

return;
}


Edited by lightxbulb

##### Share on other sites

#include <iostream>
#include <vector>
#include <cstdint> //< I cringe when I see 'int'...

// using namespace std; //< UGH! keep the namespace imho.

int32_t computeFibonacciNumber(int32_t); //< camel case

// Recursive functions  //< a crap comment. I don't need to know this to use it.
void constructFibonacciArray(std::vector<int32_t>& inputArray, int32_t index); //< descriptive function names
void writeIntArray(const std::vector<int32_t>& array);

int main()
{
int32_t fibIndex = 0;
std::vector<int32_t> fibArray; //< globals are bad M'KAY!

std::cout << "Enter an index for the Fibonacci number you want: ";
std::cin >> fibIndex;

std::cout << "Here's the number at that FibIndex: " << getFibNumber(fibIndex) << std::endl;

std::cout << "Enter the index up to where you want the Fibonacci numbers: ";
std::cin >> FibIndex;

std::cout << "Here're the first " << (fibIndex + 1) << " Fibonacci numbers: " << std::endl;

arrayFib(fibArray, fibIndex);

writeIntArray(fibArray);

return 0;
}

int32_t computeFibonacciNumber(int32_t index)
{
if(index < 2)
{
return index;
}

// no need for else here

return computeFibonacciNumber(index - 2) + computeFibonacciNumber(index - 1);
}

void constructFibonacciArray(std::vector<int32_t>& inputArray, int32_t index)
{
switch(index)
{
case 0:
inputArray.push_back(0);
break;

case 1:
inputArray.push_back(0);
inputArray.push_back(1);
break;

default:
// Recursion
constructFibonacciArray(inputArray, index - 1);
inputArray.push_back(inputArray[index - 2] + inputArray[index - 1]);
break;
}
}

void writeIntArray(const std::vector<int32_t>& array)
{
if(array.size())
{
std::cout << array[0];
for(size_t i = 1, n = array.size(); i != n; ++i)
{
std::cout << ", " << array;
}
std::cout << " The End!" << std::endl; //< pointless cruft.
}
}


##### Share on other sites

A few more explanations would help.

Why do you hate int so much - because it can be different on different systems?

And why did you remove the namespace - is it because you think there may arise a problem with identifiers mismatch?

Forget the crap comments - they are mostly so I can see why I coded this - this is not supposed to be "used", it was just an exercise.

I guess the main points are that I should have passed vector by reference rather than using a global(I guess I should have done this but seeing as it's a really small app I guess I just didn't bother - though I guess it's good practice to get used to not declaring globals when they are not really needed) and giving more descriptive names to my variables/functions etc.

Btw I wonder about the "//no need for else here" - I think it improves readability with else - or is it just me?

And is there some special reason why you changed my control structures from if() to switch()?

And why exactly do you use camel case for everything?

Thanks for the critique   - I really want to learn to code "properly" early on rather than fixing my style later.

After I finish the book on C++ I'm reading I'll probably go for Effective C++ or Exceptional C++ - I'd be happy to know if you have any more suggestions!

/edit:

I see you removed the cin.sync() and cin.ignore() at the end - I'm using them to keep my console up.

Edited by lightxbulb

##### Share on other sites

Maybe not a glaring mistake, but it can be a good habit to have in mind:

If you re-order the if-cases, you will optimize away two compares and jumps in the common case. that is, test for index >= 2 first.

(I'd use the if over switch in this case, just to have control over this)

Edited by Olof Hedman

##### Share on other sites

Why do you hate int so much - because it can be different on different systems?

I just prefer the standard sized ints - a uint64_t requires less brain power than unsigned long long...

And why did you remove the namespace - is it because you think there may arise a problem with identifiers mismatch?

'using namespace std' is plain lazy. Removing any namespace makes life a little trickier if you need to move code between cpp & header files (and it's just sloppy technique). Doing something like this is better (although I personally find it a bit annoying):

namespace MyAnimLib
{
using MyMathLib::Vec3;
};

I guess the main points are that I should have passed vector by reference rather than using a global(I guess I should have done this but seeing as it's a really small app I guess I just didn't bother - though I guess it's good practice to get used to not declaring globals when they are not really needed) and giving more descriptive names to my variables/functions etc.

Globals are fixed points in code. Any code that uses *any* globals is a bitch to maintain and refactor.

And why exactly do you use camel case for everything?

Just function names and variables. Most people tend to use PascalCase for classes. It just makes it easier to see which identifiers are types, and which are variables/function calls. Is the following a function call, or a call to a constructor? It's difficult to tell if PascalCase is used everywhere...

foo = FibNumber(1);

I'm using them to keep my console up.

I can see the reason for it, but in VC++, you can keep it open by just running the program (instead of debugging it). the sync/ignore doesn't really add anything imho (and stuff like that can easily be forgotten, causing untold annoyances and extra debugging later on....)

Edited by RobTheBloke

##### Share on other sites

Thanks a lot for the valuable advice guys!

Edited by lightxbulb

##### Share on other sites
The simple, easy-to-read recursive Fibonacci implementation is horribly inefficient, so it's not something you'd want to actually use other than casually for small numbers. The array-building recursive implementation is totally pointless because it isn't even easier to read than the iterative one.

As far as your functions go: before putting any generic or semi-generic verb like "compute" or "do" or "construct" in a function name, consider carefully if it actually adds anything. Same goes for types like "array" in function names.

Try to use actual return values in functions when it is feasible. Let the function prototype tell its story.

Applying those things to "constructFibonacciArray":
typedef uint_fast32_t uint;

std::vector<uint> fibonacci_up_to(uint n) {
++n;
std::vector<uint> v(n);
v[0] = 0; v[1] = 1;
for (uint i = 2; i < n; ++i)
v = v[i-1] + v[i-2];
return v;
}
...
auto fibs = fibonacci_up_to(40);
This reads much better, and the new function prototype also fixes several ambiguities. We no longer have to wonder whether the function produces a n-size array of numbers or numbers up to fib(n) (which is a n+1-size array). When the function was passed in a reference to vector, it was also ambiguous whether the function clears the vector, assumes it to be empty, or assumes the vector is already large enough.

On the other hand if you wish to fill existing containers with Fibonacci numbers, it's best to do it by taking in an iterator or a pair of iterators, like standard library algoritms std::fill and std::fill_n.

##### Share on other sites

Consider the fact that this was especially an exercise on recursivity - I just used it for Fibonacci numbers because that was in the examples. Just wanted to get some experience on writing a recursive function.

Edited by lightxbulb

##### Share on other sites

Consider the fact that this was especially an exercise on recursivity - I just used it for Fibonacci numbers because that was in the examples. Just wanted to get some experience on writing a recursive function.

Next, try writing an efficient recursive fib function (no cheating: no globals, no pointers, no references) that calls itself only n or fewer times to compute fib(n).

##### Share on other sites
I couldn't resist this one.
After 5 minutes I came up with this, and a quick unit test confirms that it gives the correct results:
unsigned int recursiveFib(unsigned int index, unsigned int a = 0, unsigned int b = 1)
{
....if (index == 0)
........return 1;
....return a + recursiveFib(index - 1, b, a + b);
}

1. 1
2. 2
3. 3
Rutin
22
4. 4
frob
16
5. 5

• 9
• 33
• 13
• 12
• 10
• ### Forum Statistics

• Total Topics
632579
• Total Posts
3007165

×