• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
lightxbulb

Recursive functions - code critique?

12 posts in this topic

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
1

Share this post


Link to post
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[i];
        }
        std::cout << " The End!" << std::endl; //< pointless cruft.
    }
}
2

Share this post


Link to post
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 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
1

Share this post


Link to post
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
1

Share this post


Link to post
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[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.
2

Share this post


Link to post
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.smile.png

Edited by lightxbulb
1

Share this post


Link to post
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.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).
0

Share this post


Link to post
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:
(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);
}
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
Yeah zero should not be in the sequence. It starts with two 1's.
0

Share this post


Link to post
Share on other sites

// ..

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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0