C#•5w ago

recursion

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

81 Replies

'brella boyOP•5w ago

ive got this so far but thats it

danilwaffle•5w ago

you miss THE thing recursion

jcotton42•5w ago

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

'brella boyOP•5w ago

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

jcotton42•5w ago

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

'brella boyOP•5w ago

...

jcotton42•5w ago

plus the base cases 1 and 0

danilwaffle•5w ago

i actually forgot this

'brella boyOP•5w ago

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

danilwaffle•5w ago

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

jcotton42•5w ago

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

'brella boyOP•5w ago

mkay

jcotton42•5w 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 boyOP•5w 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 boyOP•5w ago

so is this fine?

'brella boyOP•5w ago

im ngl im barely understanding my own code

jcotton42•5w 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 boyOP•5w ago

idek what that is! but thanks

jcotton42•5w ago

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

'brella boyOP•5w 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•5w ago

it gives 2, not 3

'brella boyOP•5w ago

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

jcotton42•5w 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 boyOP•5w ago

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

jcotton42•5w ago

yes

'brella boyOP•5w ago

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

jcotton42•5w ago

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

'brella boyOP•5w ago

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

'brella boyOP•5w ago

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

jcotton42•5w ago

were you told to use an array?

'brella boyOP•5w 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•5w 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 boyOP•5w 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•5w 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 boyOP•5w ago

OOOH x++ right wait no uh

'brella boyOP•5w ago

...?

jcotton42•5w ago

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

'brella boyOP•5w ago

so... uh

jcotton42•5w ago

there's a second int variable in that code snippet

'brella boyOP•5w ago

int[100]?? or i

jcotton42•5w ago

i

'brella boyOP•5w ago

right

'brella boyOP•5w ago

so.. this?

jcotton42•5w ago

you're still setting [x] every time

'brella boyOP•5w ago

oops

'brella boyOP•5w ago

so this?

'brella boyOP•5w ago

what does this even do 😭

jcotton42•5w ago

try it and see

'brella boyOP•5w ago

jcotton42•5w 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 boyOP•5w ago

this is new

'brella boyOP•5w ago

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

jcotton42•5w ago

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

'brella boyOP•5w ago

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

jcotton42•5w 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 boyOP•5w ago

jcotton42•5w ago

those are not valid indicies, so you get an IndexOutOfRangeException

'brella boyOP•5w ago

so i start with 2

jcotton42•5w ago

yes, you already set what 0 and 1 are anyhow

'brella boyOP•5w ago

ok im trying it again moment of truth

jcotton42•5w 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 boyOP•5w 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•5w ago

$code

MODiX•5w 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 boyOP•5w 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 boyOP•5w ago

and these r my outputs

Moonlit•5w 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•5w ago

your functions appear to disagree with each other

'brella boyOP•5w 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•5w ago

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

jcotton42•5w ago

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

'brella boyOP•5w ago

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

jcotton42•5w 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 boyOP•5w ago

YOURE A GODSEND 🙏

'brella boyOP•5w 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•5w 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 boyOP•5w 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•5w 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•5w ago

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

Moonlit•5w ago

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

Gaming

Programming

recursion