Jump to content

  • Log In with Google      Sign In   
  • Create Account

Recursive functions - code critique?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
12 replies to this topic

#1 lightxbulb   Members   -  Reputation: 1020

Like
1Likes
Like

Posted 30 April 2013 - 03: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[i] << ", ";
	}

	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)


Edited by lightxbulb, 30 April 2013 - 03:20 AM.


Sponsor:

#2 RobTheBloke   Crossbones+   -  Reputation: 2341

Like
2Likes
Like

Posted 30 April 2013 - 04: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[i];
        }
        std::cout << " The End!" << std::endl; //< pointless cruft.
    }
}


#3 lightxbulb   Members   -  Reputation: 1020

Like
1Likes
Like

Posted 30 April 2013 - 05: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 smile.png  - 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!smile.png

 

/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, 30 April 2013 - 05:41 AM.


#4 Olof Hedman   Crossbones+   -  Reputation: 2949

Like
1Likes
Like

Posted 30 April 2013 - 06:25 AM

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, 30 April 2013 - 06:29 AM.


#5 RobTheBloke   Crossbones+   -  Reputation: 2341

Like
3Likes
Like

Posted 30 April 2013 - 06:53 AM

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, 30 April 2013 - 06:54 AM.


#6 lightxbulb   Members   -  Reputation: 1020

Like
0Likes
Like

Posted 30 April 2013 - 07:34 AM

Thanks a lot for the valuable advice guys!smile.png


Edited by lightxbulb, 30 April 2013 - 07:43 AM.


#7 Yrjö P.   Crossbones+   -  Reputation: 1412

Like
2Likes
Like

Posted 30 April 2013 - 02: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[i] = 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.

#8 lightxbulb   Members   -  Reputation: 1020

Like
1Likes
Like

Posted 30 April 2013 - 02: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.smile.png


Edited by lightxbulb, 30 April 2013 - 02:30 PM.


#9 Yrjö P.   Crossbones+   -  Reputation: 1412

Like
0Likes
Like

Posted 30 April 2013 - 03: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.smile.png

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

#10 iMalc   Crossbones+   -  Reputation: 2314

Like
0Likes
Like

Posted 01 May 2013 - 12: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);
}

"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#11 rip-off   Moderators   -  Reputation: 8727

Like
0Likes
Like

Posted 01 May 2013 - 05: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.


#12 iMalc   Crossbones+   -  Reputation: 2314

Like
0Likes
Like

Posted 01 May 2013 - 01:27 PM

Yeah zero should not be in the sequence. It starts with two 1's.
"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#13 Chad Smith   Members   -  Reputation: 1143

Like
0Likes
Like

Posted 01 May 2013 - 11:29 PM

// ..

int32_t computeFibonacciNumber(int32_t); //< camel case

// ..

I think all your other comments, suggestions, and changes are appropriate for a review, I don't know if telling someone to use camel case is a valid review but more than likely an opinion.  Mostly because we all have our different coding styles and we all have our reasons why we think it's best.

 

Just my opinion I guess, since I'd say his style is a valid coding style






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS