CODEWITHSUNDEEP
c#algorithmrecursiondata-structures
sfhdfh
sfhdfh

Reputation: 17

How does recursion work in this small problem in C#?

So iam looking at this short piece of code using recursion to computer powers and if i give it a value of Riase_2(2,4) it returns 16 which is correct.However iam confused on how whe we reach exp==0 it returns 16 and not just 1? also how does the abase * Raise_2(abase, exp-1) work what is the abase ebing times by? Hope someone can clear this up for me thanks.

static int Raise_2(int abase, int exp)
{
    Console.WriteLine($"Loops 2 : {abase} {exp}");
    int outerLoop = 0;
    if (exp == 0)
    {
        return 1;
    }
    else
    {
        outerLoop++;
        return abase * Raise_2(abase, exp - 1);
    }
}

Upvotes: 0

Views: 62

Answers (2)

user1196549
user1196549

Reputation:

We want to check that Raise does return the value of abase^exp where both abase and exp are integers.

First notice that if exp is 0, the function returns 1, which is indeed abase^0.

Then assume that the function works correctly for exp-1 (i.e. it does return abase^(exp-1)). If you call the function Raise(abase, exp), it computes abase.abase^(exp-1), which is equal to abase^exp. Hence by induction, the function works for all integers (unless overflow occurs).

For integers, overflow can soon arise: Raise(2, 32) will, as well as Raise(3,20), Raise(4, 16), Raise(5, 14)...

Upvotes: 1

jvrn3
jvrn3

Reputation: 610

If you run with Raise(2,4), the computation works as followed:

2 * Raise(2,3)
==
2 * 2 * Raise(2,2)
==
2 * 2 * 2 * Raise(2,1)
==
2 * 2 * 2 * 2 * Raise(2,0)
==
2 * 2 * 2 * 2 * 1 = 16

Maybe you can understand that better with a debugger.

Upvotes: 2

Related Questions