C
C#

help

Fibonacci in recursive ?

Yyatta2/4/2023
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.
Eero2/4/2023
try returning a or b in the normal version?
Yyatta2/4/2023
not really need to return them, i can check them in debug mode
Eero2/4/2023
there you go, right?
Yyatta2/4/2023
i dont even know what you mean ...
Eero2/4/2023
b is 55 which is what FibRec returns which is also the correct result F_10 is 55
Eero2/4/2023
LLPeter19972/4/2023
@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
Eero2/4/2023
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)
LLPeter19972/4/2023
debatable But the two I wrote are equivalent Please tell me about my bad practices
Eero2/4/2023
it's just not debatable at all
LLPeter19972/4/2023
I'd love to hear them as a professional + compiler dev in the industry 😄
Eero2/4/2023
lol ooo look at me, i'm so good, that means everything i do is right sunglas
LLPeter19972/4/2023
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?
Eero2/4/2023
congrats to you too? must've really taken a lot of brain power that one
LLPeter19972/4/2023
Well, you didn't manage, so decided to help in 😄
Eero2/4/2023
i did, but sure just complete delusion lol
LLPeter19972/4/2023
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
Eero2/4/2023
how does it not matter? you changed their code to work differently from what they need
LLPeter19972/4/2023
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
Eero2/4/2023
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
LLPeter19972/4/2023
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
Eero2/4/2023
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
LLPeter19972/4/2023
Please do I'd love to learn from the uhm.... more experienced 😄
Eero2/4/2023
yes, please more condescending comments like that
LLPeter19972/4/2023
Soooo... you're not gonna tell me
Eero2/4/2023
if that wasn't clear yet
LLPeter19972/4/2023
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
Eero2/4/2023
how does it have anything to do with ego...?
LLPeter19972/4/2023
It's fine if you wanted to point these out But you could have said: keep in mind, Fibonacci starts from 0
Eero2/4/2023
i didn't even involve myself at all... is that not basically what i did lol
LLPeter19972/4/2023
Definitely not an initiative because you feel like someone pissed on your territory
Eero2/4/2023
how? like at all i just pointed out that fib starts at 0 lol
LLPeter19972/4/2023
And made a passive-agressive comment about my lots of bad practices And how I apparently lied "lol"
Eero2/4/2023
sure nothing to do with feeling attacked or whatever
Eero2/4/2023
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:...
Eero2/4/2023
here this is what i think of you
LLPeter19972/4/2023
That's... extremely mature
Eero2/4/2023
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
Ccanton72/4/2023
Can we all at least agree that recursive fibonacci implemented in that way is twice as expensive as it needs to be :D?
LLPeter19972/4/2023
No It's exponential my man You recursively duplicate the tree, so it's not exactly twice. It's like twice every step!
Ccanton72/4/2023
Yep, right you are
LLPeter19972/4/2023
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 :^)
Ccanton72/4/2023
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
LLPeter19972/4/2023
Yep, you invented recursion with an accumulator The fun in that is that compilers can usually turn these into loops instead of recursion
Ccanton72/4/2023
Yay, go me Depends on your compiler. .NET doesn't
LLPeter19972/4/2023
Not Roslyn tho, don't expect Roslyn to do tail-call optimization for you But our .NET compiler totally does
Ccanton72/4/2023
I wouldn't expect Roslyn to -- it's not optimizating. But the JIT doesn't
LLPeter19972/4/2023
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
Ccanton72/4/2023
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
LLPeter19972/4/2023
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
SScratch2/4/2023
@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.
Eero2/4/2023
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
SScratch2/4/2023
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".
Eero2/4/2023
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
SScratch2/4/2023
Then say that Instead it escalated into a lot of personal attacks on both of your parts
SScratch2/4/2023
@yatta sorry for the distraction. Did you get the answers you needed?
Yyatta2/4/2023
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
HHenkypenky2/4/2023
came here for coding answers and got a movie out of it what a deal

Looking for more? Join the community!

Want results from more Discord servers?
Add your server
Recommended Posts
✅ trying to get html linksi am trying to get links with only html types any ideas how?✅ Help with absorbing basic concepts learnedI've recently completed (sort of, I already learned the last module myself earlier) the C# course avObject that's passed in isn't recognized as an object?```cs using System; using System.Collections.Generic; class Program { public static void Main (st❔ .Net Maui [Problem with Tab from TabBar]So i have a css and a tabbar with 2 tabs in it both linked to a css styling file yet i can't seem to❔ Calling async methodHi guys. I tried to call this AzureAPI class in main program. But I got a error. I want to call thibuild errors in my functioni want to call the function until the loop ends but its giving me build errors that I'm not 100% sur❔ View cannot be found.LoginModel.cs Pages/Account/Login.cshtml Pages/Account/Register.cshtml AccountController.cs attache❔ Unsupported Media Type - Razor page```{"type":"https://tools.ietf.org/html/rfc7231#section-6.5.13","title":"Unsupported Media Type","st✅ JsonConvert debugging helpHello! I'm having a hard time figuring out how to solve an issue where JsonConvert.DeserializeObject❔ Make a sprite follow mouse while pivoting around character in UnityHi, I its hard to describe my issue by describing it since im not sure exactly what I'm looking for ❔ is Generic Repository a bad implementation of Repository Pattern?Surfing the internet I have found several articles that say it is an anti-pattern because it is an a❔ Problems with using Dotnet 6 on Windows to publish to an exe formatDotnet/C# newb here. Previously I've only done a small amount of development using the **.Net Framew❔ Using net7 documentation while targeting netstandard2.0This might be a bit of a dumb question, but is there anyway to make omnisharp/roslyn's tooltips use ❔ WPF app unit testingI am learning how to make unit tests. I built my app on .net core 6.0 and I created class library (o❔ where exactly should i put authorizationso i read a few posts on where to put authorization and most of the people agree on putting it in th❔ C# WPF playing background musicHello, I have WPF app for game launcher/updater. I wanted to add background music, so I added this cC# wpf mvvm Datagrid filter using LINQSo here I have a MVVM form. the Form contains a Datagrid which is connected to the Databank. I also ❔ Is it worth to create lazy dictionary in this case?I have following class: so as you see Add function add to the dictionary class TreeNode, it looks li❔ Going to use a listbox with a switch for something in the morning, need help with format for bothI would like to set two variables with a listbox using a switch and one variable with a second listb✅ What's your view on tool like Sonarqube?Should I learn from the code smells it captures?