Understanding Recursion for a complete beginner (Fibonacci Series)

Array · 2024-05-14T02:01:44.008Z

Hey everyone, I hope you are doing well I need some help understanding recursion, can someone explain to me how the base case of the Fibonacci sequence would occur? What would be the base case and then the recursive case?

J

Jimmacle•5/14/24, 2:03 AM

do you have a specific algorithm that you're looking at?

A

ArrayOP•5/14/24, 2:06 AM

cs private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

cs private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

cs private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

cs private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

A

ArrayOP•5/14/24, 2:07 AM

private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

private long Fibonacci(long n)
{
    //base cases
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        //recursive cases
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

//private void FibSequence(long n, string Fib)
//{
//    if (n == 0)
//        Fib = "0" + Fib;
//    else
//    {
//        Fib = Fibonacci(n).ToString() + " " + Fib;
//        FibSequence(n - 1, Fib);
//    }

//}


private string FibSequence(long n)
{            

    if (n == 0)
        return "0 ";
    else
    {                
        return FibSequence(n - 1) + Fibonacci(n).ToString() + " ";
    }

}

JJimmacle do you have a specific algorithm that you're looking at?

A

ArrayOP•5/14/24, 2:07 AM

I posted the solution but I'd like to get a better understanding on what is really happening here

J

Jimmacle•5/14/24, 2:08 AM

try running through it by hand, trace what happens when you call Fibonacci(2) for example

JJimmacle try running through it by hand, trace what happens when you call Fibonacci(2) fo...

A

ArrayOP•5/14/24, 2:36 AM

Sorry I am very new to coding, what do you mean by trace?

J

Jimmacle•5/14/24, 2:36 AM

my classes called it a "desk check"

J

Jimmacle•5/14/24, 2:36 AM

basically run the code by writing out the process on paper

J

Jimmacle•5/14/24, 2:39 AM

so for Fibonacci(2) you'd go through it like

Fibonacci(2) -> Fibonacci(2 - 1) + Fibonacci(2 - 2)

Fibonacci(2 - 1) -> Fibonacci(1) -> 1
Fibonacci(2 - 2) -> Fibonacci(0) -> 0

Fibonacci(2) -> 1 + 0
Fibonacci(2) = 1

A

ArrayOP•5/14/24, 2:39 AM

Sure, my teacher has used the example of recursion through a factorial which is understand a bit

A

ArrayOP•5/14/24, 2:40 AM

What basically happens is that the stack stores the base case as factorial 1 and 0 = 1 then each time you multiply it by 1 more then the factorials below (2 * 1)

P

Pobiega•5/14/24, 7:08 AM

the idea is that your fib(2) call makes 2 other fib calls, as such:

P

Pobiega•5/14/24, 7:11 AM

it quickly grows a lot more complex

P

Pobiega•5/14/24, 7:11 AM

P

Pobiega•5/14/24, 7:11 AM

so for

Fib(4)

Fib(4)

Fib(4)

Fib(4) there are 8 "internal" fib calls

P

Pobiega•5/14/24, 7:14 AM

we can easily demonstrate this with the following code

M

MODiX•5/14/24, 7:14 AM

Pobiega

REPL Result: Success

var fib4 = Fib(4);

int Fib(int n)
{
    Console.WriteLine($"Fib({n})");
    if (n <= 1)
    {
        return n;
    }

    return Fib(n - 1) + Fib(n - 2);
}

var fib4 = Fib(4);

int Fib(int n)
{
    Console.WriteLine($"Fib({n})");
    if (n <= 1)
    {
        return n;
    }

    return Fib(n - 1) + Fib(n - 2);
}

var fib4 = Fib(4);

int Fib(int n)
{
    Console.WriteLine($"Fib({n})");
    if (n <= 1)
    {
        return n;
    }

    return Fib(n - 1) + Fib(n - 2);
}

var fib4 = Fib(4);

int Fib(int n)
{
    Console.WriteLine($"Fib({n})");
    if (n <= 1)
    {
        return n;
    }

    return Fib(n - 1) + Fib(n - 2);
}

Console Output

Fib(4)
Fib(3)
Fib(2)
Fib(1)
Fib(0)
Fib(1)
Fib(2)
Fib(1)
Fib(0)

Fib(4)
Fib(3)
Fib(2)
Fib(1)
Fib(0)
Fib(1)
Fib(2)
Fib(1)
Fib(0)

Fib(4)
Fib(3)
Fib(2)
Fib(1)
Fib(0)
Fib(1)
Fib(2)
Fib(1)
Fib(0)

Fib(4)
Fib(3)
Fib(2)
Fib(1)
Fib(0)
Fib(1)
Fib(2)
Fib(1)
Fib(0)

Compile: 453.561ms | Execution: 76.074ms | React with ❌ to remove this embed.