/sci/ - Science & Math

[Anonymous No.3180081]

I have a conceptual trouble with this tiny basic C code:
int abc(n);
main()
{
int k;
printf("%d", abc(k));
}
abc(n)
{
if (n <= 1)
return (1);
else
return(n * abc(n-1) );
}

abc function says to check if n is smaller or equal to 1 return it as "1", else multiply n with abc( n-1)
This confuses me, its a function inside its own function inside its own function etc.

I tried with the number "4" and it resulted to 24.
So first is 4* abc(4-1)=4*3=12, second is 4* abc(3-1)=4*2=8, third is 4*abc(2-1)=4*1=4.
A total sum of 24. My problem is HOW does it remember the previous number and add it up?
I think the output should be "4", because it does all that but nowhere in the code shows that it adds up each time.
Also how it remembers to lower 'k' each time? It should be 4-1 every time, not 3-1,2-1.
It doesnt have a counter for it.
Halp.
Pic related.

[Anonymous No.3180085]

a dream within a dream within a dream

[Anonymous No.3180105]

I think its like the infinite series.

[Anonymous No.3180113]

Am on this function for the past 2 hours and i can't get my head around it.
I feel like a dumbfuck.

[Anonymous No.3180121]

bump for enlightenment

[Anonymous No.3180136]

too deep for you?

[Anonymous No.3180140]

>>3180136
Yeah, it seems am stupid.

Do you understand it?

[Anonymous No.3180146]

Welcome to intro CS.

abc(4)
4*abc(3)
4*3*abc(2)
4*3*2*abc(1)
4*3*2*1

[Anonymous No.3180168]

lol give up
>homework

[Anonymous No.3180171]

>>3180146
Yeah the calculation is right.
But i still dont get it.

In the loop there are no counters.

[Anonymous No.3180180]

>>3180168
Well its part of my study material.
But its not really homework, i dont ask for a solution, but for an understanding.
It seems beyond me why would this code work the way it works.

[Scientist !!ThFjnJh4EkH No.3180181]

>>3180081
Wow. Welcome to programming 101. I'm going to give a brief overview of functions and the common implementation technique.

There is aare hardware processor registers which are dedicated to pointing to the top of the stack, and the bottom of the current function record (let's let the stack grow up). They are called the the stack pointer and frame pointer.

When main calls the function abc, main puts any arguments needed by abc on top of the stack, using the stack and frame pointers. It puts them in a location expected by abc. This is called a function calling convention.

After that, main makes the processor jump to the code of abc. abc fixes up the stack pointer and frame pointer to point to the new function record.

abc will call itself again, putting the single argument on top of the stack. It does not overwrite the previous argument, because that corresponds to a different calling of abc. When abc calls abc, there is a function record of abc on top of a previous function record of abc. That is, each call of abc gets its own completely private and new local variables.

[Anonymous No.3180193]

>>3180181
Fuck you, I was about to post that.
But yeah, that's why, OP.

[Anonymous No.3180197]

>>3180181
save'd your post and am reading.
lets see o.*

[Anonymous No.3180210]

I remember that when I learned programming, there were tons of people who never understood the concept of recursion and how it worked.

Why is it that this simple concept is so alien for so many people?

[Scientist !!ThFjnJh4EkH No.3180227]

>>3180197
Imagine this as the basic layout:

. main -> int k, value 4

then:

. abc[1] -> argument int n, value 4
. main -> int k, value 4

then:

. abc[2] -> argument int n, value 3
. abc[1] -> argument int n, value 4
. main -> int k, value 4

then:

. abc[3] -> argument int n, value 2
. abc[2] -> argument int n, value 3
. abc[1] -> argument int n, value 4
. main -> int k, value 4

then:

. abc[4] -> argument int n, value 1
. abc[3] -> argument int n, value 2
. abc[2] -> argument int n, value 3
. abc[1] -> argument int n, value 4
. main -> int k, value 4

then:

. abc[4] -> argument int n, value 1, return value 1
. abc[3] -> argument int n, value 2
. abc[2] -> argument int n, value 3
. abc[1] -> argument int n, value 4
. main -> int k, value 4

then:

. abc[3] -> argument int n, value 2, return value 2
. abc[2] -> argument int n, value 3
. abc[1] -> argument int n, value 4
. main -> int k, value 4

then:

. abc[2] -> argument int n, value 3, return value 6
. abc[1] -> argument int n, value 4
. main -> int k, value 4

then:

. abc[1] -> argument int n, value 4, return value 24
. main -> int k, value 4

[Anonymous No.3180230]

this is called recursion when a function calls itself.
you may assume that this means infinite loop but if you structure the calls correctly it will eventually terminate
recursion can be used to simplify problems that would be incredibly complicated without it

[Anonymous No.3180242]

>>3180210
maybe cause it is more technical logic of programming rather than general logic of mathematics.

The 'special' property of the registers are unknown to the new programmer.
The newbie thinks the only way to remember a previous value is to put a counter or an argument that allows adding up to the same variable.

[Scientist !!ThFjnJh4EkH No.3180240]

>>3180230
>this is called recursion when a function calls itself.
Function call recursion, yes.

>you may assume that this means infinite loop but if you structure the calls correctly it will eventually terminate
That is retarded.

>recursion can be used to simplify problems that would be incredibly complicated without it
While the specification using function call recursion can be a little simpler, rewriting it to use dynamic memory isn't all that hard.

[Scientist !!ThFjnJh4EkH No.3180247]

>>3180242
The actual reason is that people probably have a naive understanding of how shit is compiled and run. They see a single variable in text, and assume that means a single "variable" when executing. The key is to understand that each function activation has its own copy of its local variables.

[Bruse !!QaQRJei51dt No.3180263]

>>3180242
I have to say, recursion was never a problem for me, even before I knew anything about the stack and registers and whatnot. It just seemed so... elegant. So obvious somehow.

You don't really need to know the particulars of it to understand it, just the general idea that a) a function can call itself and that b) each instance is self-contained as concerns variables.

[Anonymous No.3180270]

>>3180240
Of course you can just use a stack and recursion is no longer needed but in some cases it may be the best option.

[Scientist !!ThFjnJh4EkH No.3180275]

>>3180270
In C or C++, no. Never the best option. If your code uses unbounded recursion (that is recursion whose depth depends on program input), then your program has a bug.

[Anonymous No.3180276]

>>3180242
I remember thinking it worked the same way as a while loop, but I had no problems understanding the concept. Really as a noob programmer, I knew that there was no reason to try to figure out how stuff actually worked. I could always learn how stuff actually worked later on after grasping the general concepts.

>>3180240
>That is retarded
What is retarded?

[Scientist !!ThFjnJh4EkH No.3180286]

>>3180276
Why would you say "It's like an infinite loop", when it's not? There is no endless looping here, dude. Not unless you want to get a seg fault.

[Bruse !!QaQRJei51dt No.3180291]

>>3180270
I'd say in most cases the main reason to use recursion is to make the code easier to read. However, some things do lend themselves rather naturally to recursion - linked lists/trees and so on.

[Anonymous No.3180292]

>>3180275
I'm sorry I should have been specific I was talking about functional languages where proper tail recursion is supported
"Divide and conquer" algorithims that could potentially go beyond the depth of the call stack should be moved to a regular stack unless proper tail recursion can be used

[Anonymous No.3180296]

>>3180291
I would agree with you on that point - generally traversing tree-like data strucutres is a task that recursion is good for

[Anonymous No.3180297]

>>3180286
are you CS major?

[Anonymous No.3180304]

>>3180275
> If your code uses unbounded recursion (that is recursion whose depth depends on program input), then your program has a bug.

No, it has a limitation. But then most programs have limitations.

[Anonymous No.3180306]

>>3180286
Infinite loop as in the function will continually call itself forever until the call stack overflows
I would appreciate it if you weren't so condescending.

[Anonymous No.3180314]

>>3180286
It could potentially loop forever (infinite recursion).
Also plenty of programs loop forever(input listeners, servers etc)

[Anonymous No.3180325]

>>3180314
Yes that is a perfectly valid case for an infinitely looping program
Things like these can eventually terminate however due to internal logic or some kind of input
What I believe Scientist was speaking against was unintentional infinite looping caused by faulty logic

[Scientist !!ThFjnJh4EkH No.3180326]

>>3180297
I'm graduated, and a professional code monkey.

[Bruse !!QaQRJei51dt No.3180327]

>>3180286
If a recursive function can't be compared to an infinite loop because it hits a seg fault, then by the same logic no loop can be called infinite, because of heat death of universe. No need to be nitpicky.

[Anonymous No.3180395]

ok saved the whole page to be save.