Contrary to ryang's answer, I recommend avoiding "let" for ∀-quantification. If you want actual idiomatic English, you should not use "let". The idiomatic alternative is:
Consider/take any n ≥ a that belongs to S. Then ... Thus n+1 also belongs to S.
Therefore by induction every n ≥ a belongs to...
@PrithuBiswas: How was the machine-level explanation? Did you get it? It's the kind of thing that you don't really have to know, but it can be fun. =)
Even more amazing is how the CPU actually works to execute the instructions one by one.
@PrithuBiswas Because when the processor jumps to the start of the function code, it needs to know the input. Same for output. It is possible for the compiler to sometimes use registers to pass the input, but there are a limited number of registers so registers are reserved for loop-variables to make them as fast as possible. So in the general case, when there are not enough registers for all the variables in the program, then the compiler will use the stack to pass the function inputs/output.
Also, you cannot use registers if there is recursion.
So the compiler can only use registers if it analyzes the function code and determines that it does not truly use recursion.
Llike in your example, you cannot use a register for the input variable n.
Well, uhh.. a smart compiler could, but let's just say no for the time being.
(The smartness is called tail recursion. Lol let's not go into that.)
Or consider a function where the problem is unavoidable, say fibonacci:
fib(2) calls fib(0) first. At that point (n−1) is stored on the stack. We can't use the same register as for n, because if we do then we would lose the value of n, which fib(2) needs later for the call to fib(1).
@PrithuBiswas: In very general terms, you need a stack because the chain of pending function calls can be arbitrarily long, so you need to store them somewhere in some manner such that you can easily retrieve the last pending function call (whether when making the call or returning from the call). Such a structure is necessarily a stack (like a stack of paper).
On x86-64 Linux, the stack is given 8MB by default. Browse Ciro Santilli's answer about the memory layout of x86 Linux here: Where is the stack memory allocated from for a Linux process?.
For example, you could have something like the following:
Content Virtual address
_____...
This post has lots of unnecessary details, but it says that you could expect roughly 8 Mb of stack space. Each function call needs one 32-bit integer (4 bytes) for return address, and space for the inputs, so typically you can store >100000 function calls on the stack before it blows.
An example that bit me before was when I used recursion for a list whose length could be >1000000. That was too big, and I got stack overflow.
In computer science, it turns out that the best algorithms and data structures never seem to need recursion depth to be linear in the input size. In my case, I indeed didn't need recursion, and a while loop was good enough.
@PrithuBiswas: If you want to see stack overflow, just try running your program with input ten million.
@PrithuBiswas Seg fault is one result of stack overflow, yes.
As for the 0, it's because it overflowed the 32-bit integer.
Arithmetic is mod 2^32.
Some other languages will explicitly tell you "stack overflow", but C programs just say "seg fault" and you'd have to know that stack overflow is the most common culprit.
@PrithuBiswas So that when we jump back we will jump to 3 instructions later.
At the step that the processor reads "Store PC+3 at memory location SC.", that instruction is stored at memory location PC. So you don't want the processor to go back there.
You want it to go to the first instruction after "Jump to the first instruction of f.". That's 3 instructions later.
If you really want to be pedantic, in most CPU architectures you have to do the offset separately from the storing of PC, so it would even be +4:
Store x at memory location SC.
Increment SC.
Store PC+4 in some register r.
Store r at memory location SC.
Increment SC.
Jump to the first instruction of f.
Read u from memory location SC.
Anyway the details don't matter. As long as you understand how it can be done, that's all that matters. Different compilers will do slightly different things on different CPU architectures, so what I say here is correct for only some architectures.
No problem; I put on the same line because conceptually the two instructions belong to the same stack operation, but I guess it became confusing.
If you like this sort of technical details of computers, you might consider taking a "computer architecture" course in undergraduate if there is one. It's really interesting, like how we can actually build a circuit that actually reads the next instruction and executes it. But it's definitely not for people who prefer the abstract level. =)
@user21820 I think I understand a bit about how we use stacks for function calls:
We first store the return address and input arguments on the stack. Then we jump to the first instruction of the function. At start, we read the function input and return address from the stack and store them on some registers. After we get the function output, we store the output on the stack. Then we jump to the return address and read the output from the stack.
So my recommended path to learning this is to build the transparent D flip-flop (from the second website), and understand it by playing with the inputs, and then wrap it up in a component (Logisim allows you to do that), and build the edge-triggered D flip-flop using two of them, and understand that too. I just checked that it works as expected in Logisim. After you're done with that, from then on just use Logisim's provided D flip-flop (under "Memory").
On x86-64 Linux, the stack is given 8MB by default. Browse Ciro Santilli's answer about the memory layout of x86 Linux here: Where is the stack memory allocated from for a Linux process?.
For example, you could have something like the following:
Content Virtual address
_____...
