C#•2y ago

Fibonacci in recursive ?

So I have made 2 versions of Fibonacci calculator, one is in normal way and one is in recursive

    public static int Fib(int n)
    {
        if (n == 0) { return 0; }
        if(n == 1) { return 1; }
        int a = 0;
        int b = 1;
        int res = 0;
        for (int i = 0; i <= n-1; i++)
        {
            res = a + b;
            a = b;
            b = res;

        }
        return res;
    }

    public static int FibRec(int n)
    {
        if((n == 0) || (n == 1)) { return n; }
        else
        {
            return FibRec(n-1) + FibRec(n-2);
        }
    }

    public static int Fib(int n)
    {
        if (n == 0) { return 0; }
        if(n == 1) { return 1; }
        int a = 0;
        int b = 1;
        int res = 0;
        for (int i = 0; i <= n-1; i++)
        {
            res = a + b;
            a = b;
            b = res;

        }
        return res;
    }

    public static int FibRec(int n)
    {
        if((n == 0) || (n == 1)) { return n; }
        else
        {
            return FibRec(n-1) + FibRec(n-2);
        }
    }

When i run both the same time, the recursive version is incorrect. I tried to check for a correct version ones on the internet but strangely all the answer is quite the same as mine. I'm very weak at recursive and I absolutely have no idea what wrong with, so I'd be very grateful if any expert can point out the problem.

59 Replies

ero•2y ago

try returning a or b in the normal version?

yattaOP•2y ago

not really need to return them, i can check them in debug mode

ero•2y ago

there you go, right?

yattaOP•2y ago

i dont even know what you mean ...

ero•2y ago

b is 55 which is what FibRec returns which is also the correct result F_10 is 55

ero•2y ago

LPeter1997•2y ago

@yatta It's a simple off-by-one Your iterative simply always calculates one more element of the sequence, by the nature you wrote it For completeness' sake, here are two equivalent versions:

for (var i = 0; i < 10; ++i) Console.WriteLine($"FibRec({i}) = {FibRec(i)}, FibIter({i}) = {FibIter(i)}");

static int FibRec(int n) => n < 2
    ? 1
    : FibRec(n - 1) + FibRec(n - 2);

static int FibIter(int n)
{
    var a = 1;
    var b = 1;
    for (var i = 1; i < n; ++i) (a, b) = (a + b, a);
    return a;
}

for (var i = 0; i < 10; ++i) Console.WriteLine($"FibRec({i}) = {FibRec(i)}, FibIter({i}) = {FibIter(i)}");

static int FibRec(int n) => n < 2
    ? 1
    : FibRec(n - 1) + FibRec(n - 2);

static int FibIter(int n)
{
    var a = 1;
    var b = 1;
    for (var i = 1; i < n; ++i) (a, b) = (a + b, a);
    return a;
}

It's essentially your version, but with the fixed loop condition and a bit less branching to make it a bit easier to reason about

ero•2y ago

it should be n < 2 ? n : ... and a = 0 fibonacci starts at 0 Calling these equivalent is therefore just a lie (also just lots of bad practices)

LPeter1997•2y ago

debatable But the two I wrote are equivalent Please tell me about my bad practices

ero•2y ago

it's just not debatable at all

LPeter1997•2y ago

I'd love to hear them as a professional + compiler dev in the industry 😄

ero•2y ago

lol ooo look at me, i'm so good, that means everything i do is right sunglas

LPeter1997•2y ago

So your point is that you just wanted to make unrelated comments Meanwhile I've figured out that OPs problem is a simple off-by-one in the loop So congrats?

ero•2y ago

congrats to you too? must've really taken a lot of brain power that one

LPeter1997•2y ago

Well, you didn't manage, so decided to help in 😄

ero•2y ago

i did, but sure just complete delusion lol

LPeter1997•2y ago

I'd advise stopping at this point Fib can start at 0, can start at 1. Formally, people define it from 0 For the purpose of this question, it doesn't matter

ero•2y ago

how does it not matter? you changed their code to work differently from what they need

LPeter1997•2y ago

And my two versions are simply equivalent to eachother, didn't claim they are equivalent to OPs And you still didn't point out my bad practices Did I say to copypaste my code? I'd expect the OP to observe what the code does and go "oh, he started from 1, I'll just offset both versions" Not hard to do

ero•2y ago

they couldn't figure out what was wrong with their code, you have a lot of confidence in them you're also just introducing a bunch of unknown concepts to them so posting that code at all is completely pointless since they can't read it anyway

LPeter1997•2y ago

Recursion isn't easy, I'd expect them to play with it I'm not familiar with OPs language abilities, I just wanted to write a short sample. If they want to ask to know what a certain element does, we are kinda here to help them Or god forbid, they might learn language elements from reading others code? Where are my bad practices? You must have 30 of them collected by now

ero•2y ago

it really just feels like you needed to boast with "look how much more compact and cooler my code looks" if i tell you or not, you're not having any of it anyway it'd be a waste of energy to get into it

LPeter1997•2y ago

Please do I'd love to learn from the uhm.... more experienced 😄

ero•2y ago

yes, please more condescending comments like that

LPeter1997•2y ago

Soooo... you're not gonna tell me

ero•2y ago

if that wasn't clear yet

LPeter1997•2y ago

Look if you are starting out from your own personality that's fine But please don't assume from others who actually want to help I've told them what's wrong, gave a sample code that doesn't have the problem no more, your ego needed to attack it out of the blue

ero•2y ago

how does it have anything to do with ego...?

LPeter1997•2y ago

It's fine if you wanted to point these out But you could have said: keep in mind, Fibonacci starts from 0

ero•2y ago

i didn't even involve myself at all... is that not basically what i did lol

LPeter1997•2y ago

Definitely not an initiative because you feel like someone pissed on your territory

ero•2y ago

how? like at all i just pointed out that fib starts at 0 lol

LPeter1997•2y ago

And made a passive-agressive comment about my lots of bad practices And how I apparently lied "lol"

ero•2y ago

sure nothing to do with feeling attacked or whatever

ero•2y ago

https://youtu.be/Gri2HRoOXmE?t=13

Everyday SimpleFlips

YouTube

POV: Inside of SimpleFlip's fridge

This clip is from: https://youtu.be/Ot3CzyRIGdE Watch simpleflips live at: https://twitch.tv/simpleflips Subscribe to SimpleFlips: https://www.youtube.com/SimpleFlips This is an official SimpleFlips channel. Sharing is the nicest way to help/support! Really helps give our content a chance to new people, so it's appreciated. :) Suggest a clip:...

ero•2y ago

here this is what i think of you

LPeter1997•2y ago

That's... extremely mature

ero•2y ago

come on man, i'm trying to deescalate with a joke and you're not even having that? i feel like that's way more immature how do you have that much energy in your body to have such a nonsense argument

canton7•2y ago

Can we all at least agree that recursive fibonacci implemented in that way is twice as expensive as it needs to be :D?

LPeter1997•2y ago

No It's exponential my man You recursively duplicate the tree, so it's not exactly twice. It's like twice every step!

canton7•2y ago

Yep, right you are

LPeter1997•2y ago

Yes, this is exponential This is why if you slap on memoization, you essentially get "linear-time", like the iterative one (if we disregard lookup times, collisions in a hash-based container, ...) And why fib(50) takes a while on the recursive one without memo :^)

canton7•2y ago

Presumably you could:

(int, int) RecursiveFib(int n)
{
    if (n == 0) return (0, 0);
    if (n == 1) return (1, 0);
    var (a, b) = RecursiveFib(n - 1);
    return (a + b, a);
}

(int, int) RecursiveFib(int n)
{
    if (n == 0) return (0, 0);
    if (n == 1) return (1, 0);
    var (a, b) = RecursiveFib(n - 1);
    return (a + b, a);
}

No memoization necessary, still recursive

LPeter1997•2y ago

Yep, you invented recursion with an accumulator The fun in that is that compilers can usually turn these into loops instead of recursion

canton7•2y ago

Yay, go me Depends on your compiler. .NET doesn't

LPeter1997•2y ago

Not Roslyn tho, don't expect Roslyn to do tail-call optimization for you But our .NET compiler totally does

canton7•2y ago

I wouldn't expect Roslyn to -- it's not optimizating. But the JIT doesn't

LPeter1997•2y ago

Roslyn does things here and there but yeah, the bulk is in Ryu I think And I don't understand why they don't do TCO, it's not exactly hard or slow Most optimizations left out are because "too complex and slow to be beneficial for a JIT", yet this one is just... ignored

canton7•2y ago

IIRC it does do them, but there's no way to force it (at least from C#) And if you can't rely on TCO, then you obviously can't write stuff which depends on it, which means there's less code that would benefit, and the chicken/egg cycle continues

LPeter1997•2y ago

Yeah, the lack of like an enforceable attrib makes it hard to rely on in user code. Tho I think Goose made an assertion lib that could technically check for things like this, but it's cursed

Scratch•2y ago

@Ero you went way too far in personal attacks and that needlessly escalated the situation. And that video you linked was incredibly offensive and in no way succeeds as an attempt to "deescalate with a joke". T's first response was entirely reasonable.

ero•2y ago

i never said it wasn't just completely weird message i didn't attack anyone, if anything, i was attacked don't even remotely understand how i'm getting blamed here i also don't remotely understand how that video is "incredibly offensive" (??????????????????) i'm not trying to start anything, i don't have the mental capacity for that just genuinely confused

Scratch•2y ago

Me too. This got way escalated. I think the initial issue was you calling T's code "a lie (also just lots of bad practices)". That's very charged language that puts him on the defense. You responded with vague "it's not debatable at all".

ero•2y ago

their message was worded vaguely they said the code is equivalent which to me sounded like they meant it's equivalent to OP's not the 2 methods within their code are equivalent since saying that didn't really make sense to me

Scratch•2y ago

Then say that Instead it escalated into a lot of personal attacks on both of your parts

mtreit•2y ago

https://tenor.com/view/ron-burgundy-escalated-quickly-gif-9744555

Tenor

Scratch•2y ago

@yatta sorry for the distraction. Did you get the answers you needed?

yattaOP•2y ago

Ah ye, i should be the one sorry, i got my answer from some one above already, but i forgot to respone, my bad gurasad

Henkypenky•2y ago

came here for coding answers and got a movie out of it what a deal

Gaming

Programming

Fibonacci in recursive ?