Recusrion

[Ken]

Hello,

I have this recusrion code below I know how the looping works, but where I
get confused is with the return 1, How does it know to send the accumulated
value and not just returning the number 1 with any n input.

int recursion(int n)
{
if (n == 0) return 1;
else return n * recursion(n-1);
};


-Ken

 

[Victor Bazarov]

I have this recusrion code below I know how the looping works, but
where I get confused is with the return 1, How does it know to send
the accumulated value and not just returning the number 1 with any n
input.
int recursion(int n)
{
if (n == 0) return 1;
else return n * recursion(n-1);
};

Recursion cannot be explained, only shown. Take the 'else' part and
expand the contents. Pretend you're a compiler and you need to inline
the code in this function. (I know that recursive functions cannot be
inlined during compilation, just pretend you can and do it as if it is
during run-time)

V

 

[Jonathan Mcdougall]

Hello,

I have this recusrion code below I know how the looping works, but where I
get confused is with the return 1, How does it know to send the accumulated
value and not just returning the number 1 with any n input.

int recursion(int n)
{
if (n == 0) return 1;
else return n * recursion(n-1);
};

What's important is the 'n*recursion(n-1)' part, which does the actual
accumulation.

int main()
{
recursion(3);
}

does:

recursion(n=3)
return 3*recursion(2)
recursion(n=2)
return 2*recursion(1)
recursion(n=1)
return 1
return 2*1
return 3*2*1
return 6

Do it on a piece of paper if that's not clear enough. It's quite simple
once you understand it.


Jonathan

 

[benben]

What's important is the 'n*recursion(n-1)' part, which does the actual
accumulation.

int main()
{
recursion(3);
}

does:

recursion(n=3)
return 3*recursion(2)
recursion(n=2)
return 2*recursion(1)
recursion(n=1)
return 1
return 2*1
return 3*2*1
return 6

Do it on a piece of paper if that's not clear enough. It's quite simple
once you understand it.


Jonathan

That said, it is always good to be cautious with recursions. Where both
iteration and recursion can be used, prefer iteration over recursion.

And that, of course, excludes educational or intentional exercises...

Ben

 

[Chris Barts]

That said, it is always good to be cautious with recursions. Where both
iteration and recursion can be used, prefer iteration over recursion.

Uh, no. Do whatever is most natural given the algorithm you want to
express and let the compiler optimize everything into efficient machine
code. Handicapping yourself out of efficiency concerns is misguided
unless you have actually /profiled/ and /know/ it is unacceptably
inefficient to do things the natural way.

 

[benben]

Uh, no. Do whatever is most natural given the algorithm you want to

express and let the compiler optimize everything into efficient machine
code. Handicapping yourself out of efficiency concerns is misguided
unless you have actually /profiled/ and /know/ it is unacceptably
inefficient to do things the natural way.

Exactly! And how many times you find recursion more natural than iteration?
And how many times you find recursive code easier to maintain?

Regards,
Ben

 

[Chris Barts]

Exactly! And how many times you find recursion more natural than iteration?
And how many times you find recursive code easier to maintain?

I find it easier quite often. When dealing with trees, for example,
recursion is really the only option that doesn't bend my brain. And
mathematical operations are often defined in terms of recursion instead of
iteration.