Recursive functions - code critique?

Apr 30, 2013 at 9:16 AM

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;
}

Are there any glaring mistakes? Anything you would recommend about this? (Btw I know I named my function and array kinda bad)

128

Apr 30, 2013 at 10:56 AM

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

Author

Apr 30, 2013 at 11:25 AM

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.

alh420

115

alh420

Apr 30, 2013 at 12:25 PM

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)

128

Apr 30, 2013 at 12:53 PM

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

Author

Apr 30, 2013 at 1:34 PM

Thanks a lot for the valuable advice guys!

Stroppy Katamari

Apr 30, 2013 at 8:10 PM

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.

Author

Apr 30, 2013 at 8:30 PM

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.

Stroppy Katamari

Apr 30, 2013 at 9:54 PM

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

182

May 1, 2013 at 6:33 AM

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:
(Select the white text below to read the answer)
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);
}

rip-off

Mod

445

rip-off

May 1, 2013 at 11:38 AM

Your function is incorrect when called multiple times. Try adding a loop to the program:


int main() {
    int FibIndex = 0;
    while(cout << "Enter the index up to where you want the Fibonacci numbers: " && cin >> FibIndex) {
        cout << "Computed on demand:\n{\n\t";
        for(int i = 0 ; i < FibIndex + 1 ; ++ i) {
            if(i > 0) {
                cout << ", ";
            }
            cout << GetFibNumber(i);
        }
        cout << "\n}\n";
 
        ArrayFib(FibIndex);
        cout << "From the array: " << endl;
        PresentArray();
    }
}

Sample output:

Enter the index up to where you want the Fibonacci numbers: 0

Computed on demand:

{

0

}

From the array:

0 The End!

Enter the index up to where you want the Fibonacci numbers: 1

Computed on demand:

{

0, 1

}

From the array:

0, 0, 1 The End!

Enter the index up to where you want the Fibonacci numbers: 2

Computed on demand:

{

0, 1, 1

}

From the array:

0, 0, 1, 0, 1, 0 The End!

Enter the index up to where you want the Fibonacci numbers: 3

Computed on demand:

{

0, 1, 1, 2

}

From the array:

0, 0, 1, 0, 1, 0, 0, 1, 0, 1 The End!

Enter the index up to where you want the Fibonacci numbers: 4

Computed on demand:

{

0, 1, 1, 2, 3

}

From the array:

0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1 The End!

Enter the index up to where you want the Fibonacci numbers: 5

Computed on demand:

{

0, 1, 1, 2, 3, 5

}

From the array:

0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1 The End!

RobTheBloke's implementation also contains this bug.

182