C#•2w ago

recursion

so I need to make a fibonacci sequence using recursion but bro idk how u achieve that??

81 Replies

'brella boy•2w ago

ive got this so far but thats it

danilwaffle•2w ago

you miss THE thing recursion

jcotton42•2w ago

well, what's the definition of the fibonacci sequence? in math terms

'brella boy•2w ago

well you add the previous two terms for the new term ya idk how to implement it

jcotton42•2w ago

so fib(n) = fib(n - 1) + fib(n - 2) right?

'brella boy•2w ago

...

jcotton42•2w ago

plus the base cases 1 and 0

danilwaffle•2w ago

i actually forgot this

'brella boy•2w ago

how did i not think of this... so if n = 1 or 0 i just return 0 right

danilwaffle•2w ago

just make sure to add 0 check so you won't have stack overflow

jcotton42•2w ago

Wikipedia says fib(0) = 0 and fib(1) = 1

'brella boy•2w ago

mkay

jcotton42•2w ago

Starting from 0 and 1, the sequence begins[3] 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

< 0 is undefined, I'd throw an exception for that unless you were told you can assume n >= 0

'brella boy•2w ago

I wasn't but they didn't ask me to have validation so I'm gonna save myself the time and just not..

'brella boy•2w ago

so is this fine?

'brella boy•2w ago

im ngl im barely understanding my own code

jcotton42•2w ago

the () on the return are unnecessary same for the == true on the if I, personally, would write it like this*

// C# convention for methods is PascalCase
static int FibRecurse(int n, bool print = false)
{
    int fib;
    if (n == 0)
    {
        fib = 0;
    }
    else if (n == 1)
    {
        fib = 1;
    }
    else
    {
        fib = FibRecurse(n - 1) + FibRecurse(n - 2);
    }
    
    if (print)
    {
        // WriteLine instead of Write with an \n
        Console.WriteLine("Fibonacci = {0}", fib);
    }
    return fib;
}

// C# convention for methods is PascalCase
static int FibRecurse(int n, bool print = false)
{
    int fib;
    if (n == 0)
    {
        fib = 0;
    }
    else if (n == 1)
    {
        fib = 1;
    }
    else
    {
        fib = FibRecurse(n - 1) + FibRecurse(n - 2);
    }
    
    if (print)
    {
        // WriteLine instead of Write with an \n
        Console.WriteLine("Fibonacci = {0}", fib);
    }
    return fib;
}

*if it weren't for the print I would return directly from the if/else if/else, also would use string interpolation instead of formatting placeholders, but you might not be allowed to use those

'brella boy•2w ago

idek what that is! but thanks

jcotton42•2w ago

@'brella boy which part are you having trouble understanding?

'brella boy•2w ago

fib = FibRecurse(n - 1) + FibRecurse(n - 2); like i get that the input is having 1 minused then 2 minused then you add that but like lets say i input 3 im gonna get 3 right??? isnt that.. incorrect?? or am i misunderstanding idk i cant wrap my head around this and i kinda need to since im gonna have to do it iteratively after

jcotton42•2w ago

it gives 2, not 3

'brella boy•2w ago

its not (3-1) + (3-2)..?

jcotton42•2w ago

fib(3) = fib(2) + fib(1) fib(1) is already defined 1, so fib(2) + 1 fib(2) = fib(1) + fib(0) fib(0) is already defined as 0, so fib(2) = 1 + 0 = 1 fib(3) = 1 + 1 = 2 the function is calling itself

'brella boy•2w ago

OH so essentially it just repeats until it reaches the base case

jcotton42•2w ago

yes

'brella boy•2w ago

and then it adds those values together oh im really slow wow

jcotton42•2w ago

this would just be fib = (n - 1) + (n - 2) which is not the Fibonacci sequence

'brella boy•2w ago

so one small issue... i kinda have to do it iteratively now i tried this

'brella boy•2w ago

but nothing happened i despise and do not understand lists so thats probably the issue

jcotton42•2w ago

were you told to use an array?

'brella boy•2w ago

nope i wasnt told to use anything but i was given a template which was everythig except the for loop i added that myself so i assume i have to do it in that way

jcotton42•2w ago

:harold: you don't need a list for an iterative solution, why would they make you do that anyhow, look at the variable you're using in the array indexes in the for loop body

'brella boy•2w ago

idk man.. im NOT supposed to use x? bro this is just it i HATE lists i cant visualise them i cant work with them whenever i employ them its WRONG but i know the syntax so atp its just me

jcotton42•2w ago

well, x isn't changing during the course of that loop right? so you're setting the same array index on every iteration

'brella boy•2w ago

OOOH x++ right wait no uh

'brella boy•2w ago

...?

jcotton42•2w ago

no, x is the fib number you're looking for

'brella boy•2w ago

so... uh

jcotton42•2w ago

there's a second int variable in that code snippet

'brella boy•2w ago

int[100]?? or i

jcotton42•2w ago

i

'brella boy•2w ago

right

'brella boy•2w ago

so.. this?

jcotton42•2w ago

you're still setting [x] every time

'brella boy•2w ago

oops

'brella boy•2w ago

so this?

'brella boy•2w ago

what does this even do 😭

jcotton42•2w ago

try it and see

'brella boy•2w ago

jcotton42•2w ago

int[] fiblist delcares a variable fliblist with a type of int array new int[100] makes an int array of size 100 and then the = assigns that new array to fiblist

'brella boy•2w ago

this is new

'brella boy•2w ago

so fiblist is an array of size 100 mk that was throwing me off ty

jcotton42•2w ago

yes, with indicies from 0 to 99 (since arrays start from 0)

'brella boy•2w ago

wait so whats the problem with this is it the fact that the array is only size 100

jcotton42•2w ago

for (int i = 0 your index var starts with 0 but in the loop body, you try to index into i - 1 and i - 2, which is -1 and -2

'brella boy•2w ago

jcotton42•2w ago

those are not valid indicies, so you get an IndexOutOfRangeException

'brella boy•2w ago

so i start with 2

jcotton42•2w ago

yes, you already set what 0 and 1 are anyhow

'brella boy•2w ago

ok im trying it again moment of truth

jcotton42•2w ago

(in case you haven't been taught about exceptions, it's how C# deals with errors, your course will cover them eventually if it's any good)

'brella boy•2w ago

it does surprisingly but anyways i think it worked let me send the full program i didnt before because i dont know what it does 💀

jcotton42•2w ago

$code

MODiX•2w ago

To post C# code type the following: ```cs // code here ``` Get an example by typing $codegif in chat For longer snippets, use: https://paste.mod.gg/

'brella boy•2w ago

public class Program
{

    public static void Main()
    {
        Stopwatch sw = new Stopwatch();

        for (int x = 5; x < 50; x = x + 5)
        {
            sw.Reset();
            sw.Start();
            int fib = fibrecurse(x, false);
            sw.Stop();
            Console.WriteLine("Recursive {1}th Fib={2}, Elapsed={0}", sw.Elapsed, x, fib);
        }
        Console.WriteLine("\n\n");

        for (int x = 5; x < 50; x = x + 5)
        {
            sw.Reset();
            sw.Start();
            int fib = fibiterate(x, false);
            sw.Stop();
            Console.WriteLine("Iterative {1}th Fib={2}, Elapsed={0}", sw.Elapsed, x, fib);
        }
    }
    //
    // Return the xth fibanacci number using recursion
    // If print set to true, print out debug 
    //
    static int fibrecurse(int x, bool print = false)
    {
        int fib = 0;

        if (x == 0){
            fib = 0;
        }

        else if (x == 1){
            fib = 1;
        }


        else{
            fib = fibrecurse(x - 1) + fibrecurse(x - 2);
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fib);
        return (fib);
    }
    //
    // Return the xth fibanacci number using iteration
    // If print set to true, print out debug 
    //
    static int fibiterate(int x, bool print = false)
    {
        int[] fiblist = new int[100];

        fiblist[0] = 0;
        fiblist[1] = 1;

        for (int i = 2; i < (x + 1); i++){

            fiblist[i] = fiblist[i - 1] + fiblist[i - 2];
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fiblist[x - 1]);
        return (fiblist[x - 1]);
    }
}

public class Program
{

    public static void Main()
    {
        Stopwatch sw = new Stopwatch();

        for (int x = 5; x < 50; x = x + 5)
        {
            sw.Reset();
            sw.Start();
            int fib = fibrecurse(x, false);
            sw.Stop();
            Console.WriteLine("Recursive {1}th Fib={2}, Elapsed={0}", sw.Elapsed, x, fib);
        }
        Console.WriteLine("\n\n");

        for (int x = 5; x < 50; x = x + 5)
        {
            sw.Reset();
            sw.Start();
            int fib = fibiterate(x, false);
            sw.Stop();
            Console.WriteLine("Iterative {1}th Fib={2}, Elapsed={0}", sw.Elapsed, x, fib);
        }
    }
    //
    // Return the xth fibanacci number using recursion
    // If print set to true, print out debug 
    //
    static int fibrecurse(int x, bool print = false)
    {
        int fib = 0;

        if (x == 0){
            fib = 0;
        }

        else if (x == 1){
            fib = 1;
        }


        else{
            fib = fibrecurse(x - 1) + fibrecurse(x - 2);
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fib);
        return (fib);
    }
    //
    // Return the xth fibanacci number using iteration
    // If print set to true, print out debug 
    //
    static int fibiterate(int x, bool print = false)
    {
        int[] fiblist = new int[100];

        fiblist[0] = 0;
        fiblist[1] = 1;

        for (int i = 2; i < (x + 1); i++){

            fiblist[i] = fiblist[i - 1] + fiblist[i - 2];
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fiblist[x - 1]);
        return (fiblist[x - 1]);
    }
}

'brella boy•2w ago

and these r my outputs

Moonlit•2w ago

I've been enjoying reading this and I won't step on Bewares toes, but.. I would suggest that you kind of set a standard of how you want to write and then stick to it. Like either don't includes {} for single lines or do. EG you use 2 different styles here

        for (int i = 2; i < (x + 1); i++){

            fiblist[i] = fiblist[i - 1] + fiblist[i - 2];
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fiblist[x - 1]);

        for (int i = 2; i < (x + 1); i++){

            fiblist[i] = fiblist[i - 1] + fiblist[i - 2];
        }

        if (print == true)
            Console.Write("Fibanacci = {0}\n", fiblist[x - 1]);

It'll help you with reading your own code. If you're new I suggest just always including the {}

jcotton42•2w ago

your functions appear to disagree with each other

'brella boy•2w ago

oh thats cause i literally didnt write the bottom half its a template yeah thats what im not getting did that sound rude? sorry

Moonlit•2w ago

No no it's fine, I should have been more attentive

jcotton42•2w ago

I think you want fiblist[x] instead of x - 1 for the iterative yeah

'brella boy•2w ago

funny cause that was a part of the template but ill try it 😭

jcotton42•2w ago

because right now your array is set up to have index n = fib term n but you're asking for term n - 1 at the end

'brella boy•2w ago

YOURE A GODSEND 🙏

'brella boy•2w ago

THANK YOU one last favour though wait no nvm i think i actually understand for once the two indexes before the index at i get added together oh right i know whats confusing me how comes returning x works if i was working with i the entire time

jcotton42•2w ago

when you were working with i in that for loop, you were filling up the array with the fibonacci terms but x is the term you were looking for i'm surprised they made you use an array for the iterative solution tho

'brella boy•2w ago

OOOH SO I FILL UP THE ARRAY USING I AND THEN USE X TO ACTUALLY FIND THE POINT IN THE SEQUENCE!! or rather the array thank u!! once again

Moonlit•2w ago

Console.WriteLine("Iterative {1}th Fib={2}, Elapsed={0}", sw.Elapsed, x, fib); I didn't know you could do this Is there a reason for using this over just passing them directly in? Genuinely curious Like this? Console.WriteLine("Iterative {x}th Fib={fib}, Elapsed={Elapsed}");

jcotton42•2w ago

did you mean $"..."? string interpolation in any case, that's how you did it before C# 6 added string interpolation

Moonlit•2w ago

I didn't notice there was no $ on it But yeh Oh I see, interesting

Gaming

Programming

recursion