Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Spehss _]

Tried messing with recursion in C++ after reading about it in a book about AI stuff. Tried making a program that used a recursive function call to calculate to a certain point in the fibonacci sequence before printing the resulting number. Couldn't work it out, but on the bright side I know a bit on how vectors work now.

Anyone more experienced willing to provide an example of how they'd program this?

[TheDarkStar]

Tried messing with recursion in C++ after reading about it in a book about AI stuff. Tried making a program that used a recursive function call to calculate to a certain point in the fibonacci sequence before printing the resulting number. Couldn't work it out, but on the bright side I know a bit on how vectors work now.

Anyone more experienced willing to provide an example of how they'd program this?

I'd probably just use a function that passes a result back by reference. Something like

Code: [Select]

void Fibonacci(int* N, int* NMinusOne)
{
     int* TempN;
     &TempN = &N;
     &N = &N + &NMinusOne;
     &NMinusOne = &N;
}

int RunToFibonacciNumber(int NumberToRunTo)
{
     int* N;
     int* NMinusOne;
     &N = 1;
     &NMinusOne = 1;
     for (i = 0; i < NumberToRunTo; i++)
          Fibonacci(N, NMinusOne);
     return N;
}

It doesn't have any kind of out-of-bounds checking and could probably be optimized a bit, but it should work.

[Putnam]

Code: [Select]

#include <iostream>

int fib(int n) {
    if (n==0) {
        return 0;
    }
    if (n==1) {
        return 1;
    }
    return fib(n-1)+fib(n-2);
}

int main(){
    std::cout << fib(8);
}
This is obviously the most naive implementation of the recursive fibonacci function. Hope you like exponential algorithmic complexity!

[Spehss _]

I'd probably just use a function that passes a result back by reference. Something like

Spoiler (click to show/hide)

Code: [Select]

void Fibonacci(int* N, int* NMinusOne)
{
     int* TempN;
     &TempN = &N;
     &N = &N + &NMinusOne;
     &NMinusOne = &N;
}

int RunToFibonacciNumber(int NumberToRunTo)
{
     int* N;
     int* NMinusOne;
     &N = 1;
     &NMinusOne = 1;
     for (i = 0; i < NumberToRunTo; i++)
          Fibonacci(N, NMinusOne);
     return N;
}


It doesn't have any kind of out-of-bounds checking and could probably be optimized a bit, but it should work.

I understood most of that. I think. Except the int* part. I know & is used to refer to the memory address of a variable, didn't know & could be put before the variable name, and I don't know what * does.

Spoiler (click to show/hide)

Code: [Select]

#include <iostream>

int fib(int n) {
    if (n==0) {
        return 0;
    }
    if (n==1) {
        return 1;
    }
    return fib(n-1)+fib(n-2);
}

int main(){
    std::cout << fib(8);
}

This is obviously the most naive implementation of the recursive fibonacci function. Hope you like exponential algorithmic complexity!

I figured it would be easy so that's why I tried to figure it out myself before giving up and asking here. D:

[TheDarkStar]

Code: [Select]

#include <iostream>

int fib(int n) {
    if (n==0) {
        return 0;
    }
    if (n==1) {
        return 1;
    }
    return fib(n-1)+fib(n-2);
}

int main(){
    std::cout << fib(8);
}
This is obviously the most naive implementation of the recursive fibonacci function. Hope you like exponential algorithmic complexity!

Yeah, that one looks time-consuming for larger numbers.

[Reelya]

EDIT: @Putnam: your one will infinite loop if n < 0, so you need to either check for that or check "n<=0" instead of "n==0".

Also, because of branch prediction you should always put the most likely option at the top of your "if-else" or repeated "if" statements. This is because the compiler can't possibly know the "use-cases", i.e. the likely input values you plan to pump into your function. Maybe 99% of the inputs are zero, or maybe they're all very large numbers. Only the human designer can work that out. So it can't optimize for the order to do the tests.

Since processing a large positive number is the worst-case scenario for fibonacci, then the check for >1 should be first. This will minimize the number of CPU cycles needed to get your value. For fibonacci(1000000), the checks for n==0 and n==1 would happen for each of those, leading to 2 million comparisons, vs 1 million if you did an n>1 check first.

Tried messing with recursion in C++ after reading about it in a book about AI stuff. Tried making a program that used a recursive function call to calculate to a certain point in the fibonacci sequence before printing the resulting number. Couldn't work it out, but on the bright side I know a bit on how vectors work now.

Anyone more experienced willing to provide an example of how they'd program this?

Write out the desired function first:

f(n) = f(n-1) + f(n-2)

set some special rules for edge cases

f(0) = 1
f(1) = 1

this is the information you need to build your recursive function:

Code: [Select]

int fibonacci(int n)
{
    if(n>1)
        return fibonacci(n-1) + fibonacci(n-2);
    else if(n==1)
        return n;
    else
        return 0;
}
Done, and done.

[Levi]

After a few days of struggling to get Ruby-GTK2 working properly, I finally discovered the problem.  Windows 8 is buggy and needed a windows-update to fix things. 

There was 3 days wasted at work wasted by windows.   

[Aqizzar]

My boss is paying me to take the Microsoft Certification for HTML5/Javascript next week.  Anyone taken a cert test before?  I have no idea what I actually need to prepare for.

[Skyrunner]

Does anyone know what is it with modern Javascript library writers where they split up functionality in a million files scattered across the folder structure? How do they expect you to have like 10 script includes to draw a blank canvas? @.@ (talking about Three.js here--apparently the basic projector and the canvas renderer are in different files)

[monkey]

Code: [Select]

int fibonacci(int n)
{
    if(n>1)
        return fibonacci(n-1) + fibonacci(n-2);
    else if(n==1)
        return n;
    else
        return 0;
}

This only works for n < 40something, if I remember right.
Not saying that it is wrong, just keep in mind how a small n can produce a rabitsplosion the likes of which even Armok has never seen.

[Mephisto]

Does anyone know what is it with modern Javascript library writers where they split up functionality in a million files scattered across the folder structure? How do they expect you to have like 10 script includes to draw a blank canvas? @.@ (talking about Three.js here--apparently the basic projector and the canvas renderer are in different files)

It's easy for development to have stuff be separated. You're intended to actually use the minified file, which is basically all of them concatenated together.

[Skyrunner]

Does anyone know what is it with modern Javascript library writers where they split up functionality in a million files scattered across the folder structure? How do they expect you to have like 10 script includes to draw a blank canvas? @.@ (talking about Three.js here--apparently the basic projector and the canvas renderer are in different files)

It's easy for development to have stuff be separated. You're intended to actually use the minified file, which is basically all of them concatenated together.

The minified file is smaller than the not-minified one but still has everything? I find that kind hard to believe >.>

Edit: I tried the minified file and both of them don't work. I'm starting to think that it's because they use Node.js or something to have a requires() system...

Edit2: Oh, I think I get it now. You mean that when developing, you're expected to have a sort of system that automatically includes everything you need, and when pushing to production you use some other script to batch everything into a single minified js file. That sucks :/

[Mephisto]

Sorry, I meant "easier for the Three.js developers." If all of the code that I develop was in a single file, I would honestly probably find a different job.

The minification process removes comments, extraneous space, and newlines, as well as shortens variable names. It should function the same but it's all in a smaller file.

If three.min.js doesn't work but the non-minified version does, I'm not sure what the issue is.

[Skyrunner]

Sorry, I meant "easier for the Three.js developers." If all of the code that I develop was in a single file, I would honestly probably find a different job.

The minification process removes comments, extraneous space, and newlines, as well as shortens variable names. It should function the same but it's all in a smaller file.

If three.min.js doesn't work but the non-minified version does, I'm not sure what the issue is.

What happens is that specific functionality is in different files. The default Three.js file (nor the Three.min.js file) has everything you need to actually use Three.js. In my case. I had to include CanvasRenderer.js and Projector.js from different files.

I know that obviously code is separated into different files when developing, but a lot of the libraries I used either combined them into one file before releasing (d3.js, Victor.js), while others provide the option to have a modular file (you can include Physics.js plus all the stuff you want like bounded_box.js, impulse_collision.js, pixi_renderer.js) while also providing a pre-compiled file that has everything (Physics.mono.js).

[miauw62]

This formula returns the n^th fibonacci number
(probably not what you're looking for, though)

The naive implementation of a fibonacci sequence is pretty slow, but it illustrates the concept of recursion pretty well.
I know there's a solution that runs in linear time without using dynamic programming, but I can't remember it right now. (Not that it really matters, since that formula is obviously fastest)