---------
If I make n = 2, n will be smaller than 3 (line 3) therefore the answer would be 1.
---------
If I make n = 3, the expression will then be false (line 3) therefore line 9 will be used. fib(n-2) is one therefore when the program goes through line 3 again it will return one to fib(n-2). fib(n-1) will give n value of 2 therefore when line 3 is evalued the return value of fib(n-1) will be 1.
Conclusion: return(fib(n-2)) + fib(n-1)) will give a return value of 2.
----------
all above is very clear to me... now this is where I get very confused about where the values are stored.
----------
I thought that line 9 could return a maximum value of 2, but I am wrong.
If n = 5, line 3 is false therefore line 9 will be interpreted.
fib(5-2) will give n a value of 3 and fib(5-1) will give n a value of 4. When fib(5-2) is called and line 3 is false therefore line 9 is interpreted again but now the values are fib(3-2) and fib(3-1). When fib(3-2) goes through line 3 it returns a value of 1 and when fib(3-1) goes through line 3 it returns a value of 1. ***in total we have 1 + 1 which is 2*** After all that the program somehow magically ****ing (sorry about the swearing... I'm really mad :mad: ) remembers the fib(5-1).
fib(5-1) then goes through line 3 and since it's false line 9 is called again. This time we have fib(4-2) and fib(4-1). Now when fib(4-2) is interpreted by line 3 it has a return value of 1. Now somehow ****ing magically, this return value is stored somewhere in line 9 (WTF!?!?)
Then fib(4-1) is called and interpreted by line 3 wich then is false and the program goes to line 9. fib(3-2) and fib(3-1) are then the n values. fib(3-2) then goes to line 3 and has a return value of 1 which is somehow ****ing magically stored somewhere in line 9 and fib(3-1) goes through line 3 with a return value of 1 that is stored somewhere in line 9.
This gives me a total of *** 1 + 1 + 1 + 1 + 1 = 5 ***
I really don't understand how all of these values are stored in line 9. I would think that the values would replace eachother or I don't know... this just doesn't make any sense to me.
----------
There... I couldn't have been more specific about my problem.
Now I would ask you guys to help me out with this. Even if you don't know just say something like "sorry man... don't know how to help you" or whatever. Just so I know that this post is not ignored.
Thank you all in advence for any help :)
ps. This post is also linked to this one:
http://www.linuxnewbie.org/cgi-bin/ubbcgi/ultimatebb.cgi?ubb=get_topic&f=14&t=003403
[ 02 August 2001: Message edited by: sincka ]
jemfinch
08-02-2001, 02:44 AM
Here's the way recursion was poetically described to me:
A recursive function has two essential ingredients: a "base case" and a "smaller caller". The "base case" is the case that your function should eventually get to: in the case of a fibonacci generator, it's when n < 2. The "smaller caller" is the call to the function that reduces its arguments toward the "base case". That's why you see fib (n-1) and fib (n-2) in all those fibonacci implementations: they're the "smaller caller" and they're reducing n until it gets to the "base case".
Maybe that'll help. If not, well, I don't know, you'll get it someday :)
Jeremy
sincka
08-02-2001, 02:49 AM
Thanx for the reply Jemfinch :)
Yes... I am aware of the 'base case' thingy... just didn't know what the term for it was :p
Again... my understanding with recursion is:
how can line 9 return more than a value of 2? Since line 9 is used multiple times to get a higher number than 2. Are the numbers stored temporarely somewhere in the memory? Is this magic? I'm seriously about to pull out some tissue and start crying like a 2 year old girl.
andrzej
08-02-2001, 03:33 AM
Let's start with n=5.
function fib (call it fib5) launches 2 instances of function fib, one with n=3 and second with n=4.
Let's enter (like the program does) function fib with n=3 (fib3a). This function lauches 2 instances of function fib, one with n=1 (fib1a) and second with n=2 (fib2a).
Function fib1a returns immediately 1. So does fib2a.
fib3a returns fib1a+fib2a = 2;
We're now back in fib5 and we enter fib4, which launches fib2b and fib3b. fib2b returns 1. fib3b works exactly the same as fib3a therefore it returns 2.
fib4 returns fib2b+fib3b = 1 + 2 = 3;
fib5 returns fib3a + fib4 = 2 + 3 = 5;
Let's check it. Fibonacci numbers are: 1,1,2,3,5,8...
Yep, fib(5)==5.
All the intermediate results are stored somewhere on the stack - when fib5 launches fib4, or fib3, it saves the whole context on the stack. When it starts fib3, the result from fib4 is already available and is saved on the stack.
I hope you can understand something from all this writing. :o
jemfinch
08-02-2001, 04:01 AM
Originally posted by sincka:
Are the numbers stored temporarely somewhere in the memory?
Yes, they are. They're stored in the program stack.
As your program runs, it keeps a stack (that's a LIFO datatype, "Last in, First out", where stuff you stick in comes out in the opposite order that you stuck it in; you "push" things onto a stack, and you "pop" them off. Think of a stack of plates -- you keep putting one plate on top, and then, when you want a plate you take one off the top.) of function calls. As long as you keep calling functions, it keeps adding those calls to the stack.
Whenever you call a function (any function, not just a recursive one) it pushes that function with its arguments and local variables onto the stack. From there (that "stack frame") it does all the cool stuff functions do -- modify variables, add stuff, subtract stuff, branch, whatever. At the top of that stack is where the function "lives". Every time your function calls another function, though, it is put into suspended animation while that function (the one that was called) is pushed onto a stack and starts doing its work.
Now, when functions are called, generally they do some work and then return some value. So when your function calls another function, it expects some value to be returned, and generally puts that value in a variable or something. So when the function on the top of the stack finishes running, and finally returns a value, it's popped from the stack, and the value is given to the function that just became the top of the stack, to do with it what it wishes.
And so the program stack goes; functions called are pushed, evaluated, and their values returned to the functions that called them. Understanding this is the key to understanding how numbers are stored temporarily in memory.
There's nothing different, program-stack-wise, between a recursive function and a regular function. The only difference is that a regular function is guaranteed to return, whereas a recursive function must be designed with a proper base case and smaller caller in order to return.
So, we come to your question, "Are the numbers stored temporarily somewhere in the memory?". Yes, they are. They're stored on the program stack. When the "fib" function says, "fib(n-2) + fib(n-1)" it's really just saying, "return the value of fib(n-2) plus fib(n-1)" and so the program stack handles that.
Fibonacci isn't a good first recursion lesson. I prefer factorial. You remember factorial? n! = n * (n-1) * (n-2) ... Yeah, it's a great way to teach recursion. Normally, you'd code it iteratively:
def fact(n):
i = 1
while n > 0:
i = i * n
n = n - 1
return i
However, it can also be coded recursively really easily, and lets you see more clearly how recursion works:
def fact(n):
if n == 0:
return 1
else:
return n * fact(n-1)
See how that replicates the definition of factorial? The factorial of 'n' is n times (n-1) times (n-2) ... down to 0, whose factorial is defined as 1. With respect to the program stack, look at the recursive return statement: "return n * fact(n-1)". When the function calls itself, it is put into suspended animation for awhile, but the value "n" is saved until it can be multiplied by the return value of "fact(n-1)". So when "n" finally gets down to 0, fact functions stop getting pushed onto the stack and start getting popped, each with their own little stored "n" being multiplied by the return value of the "fact" function that they called. Eventually, it'll get to the top of the stack, where "fact" was originally called, and then it'll return a value to whatever function called "fact".
Once you've got "fact" down, you shouldn't have any trouble understanding where the values for "fib" are stored at.
Jeremy
Niminator
08-02-2001, 05:47 AM
I think the best way to understand how a recursive function works in c is to explain what's happenning on the actual cpu. Take what I've put below as added to what Jemfinch already said, with just a little more on the technical side. You basically have to understand the following stuff;
-------
The intel-based processor has a native stack that is used, and although it's implemented as lifo, it isn't super-strict about it. In other words, if I want to go into some spot on the stack, I don't actually have to pop all of the stack items off, I can go directly to it and 'read' it. For reasons I don't understand, the stack is started at a high memory location, and works its way down over time.
C uses this stack and a 32-bit memory location, called the ebp register, on the actual cpu to call C functions. C uses a second 32 bit register, called eax, to return values.
Memory on the Intel processor is assigned addresses in 8 bit chunks, called bytes. In other words, memory location 1 actually points at the start of the first bit in memory, and memory location 2 actually points to the 9th bit in memory
------
Also, keep in mind, the memory locations for code and program variables are separate, and not mixed together; when you say that information is stored 'on line 9' it's like saying Linux instead of GNU/Linux; people will think you're not an ubergeek. :rolleyes:
The best way to describe this is probably to use an example.
using the code you provided and the example of the number 3==n, let's follow the steps the processor goes through.
when fib(int n) is called the first time, the following things happen;
1. n (this is the actual number 3, not an address pointing to 3) is pushed onto that stack, and the stack pointer is decremented by 4 bytes (assuming int is a 32 bit integer)
2. the next step in the currently running code is pushed onto the stack. This is a 32 bit memory address, so the stack pointer is again decremented 4 bytes. Understand that this isn't the next step in the fib function, but the instruction that will be run when the processor completes the fib function, and also where jemfinch's 'suspended animation' actually takes place. This value is the computer's way of remembering where the code should pick up again when the function is complete.
3. Just in case that value stored in ebp was important (and in a recursive function, it's very important), it's pushed too, and again the stack is decremented 4 bytes.
4. Finally, the current top of the stack saved in the ebp register.
We now have what's called a 'stack frame'. I'll list exactly what's stored in there at this step.
[ebp]; old ebp value
[ebp+4]; next instruction
[ebp+8]; value of n
All of that is prep work for the c function to execute. It compares the value in [ebp+8] (3) to 3.
At this point, just trust that I will explain how the 'return' is happenning. when I've listed the rest of the steps the code goes through.
Since n is not less than 3, it follows the above 4 steps for n-2, and compares that to 3. Since n-2 is less than 3, it returns 1, and then runs through the above 4 steps for n-1 and once again compares n-1 to 3. Since it's also less than 3, it returns 1 as well. Now you've got these 2 1's, which it adds together, and returns as well.
So how does the computer magically remember the values in each step? Well, it uses that stack frame, created for each iteration of the function. On the last call, when n<3 is finally true, each of the recursive functions unwinds, using the old ebp to 'remember' where it was pointing at in the stack, and the next instruction stored in step 2 to 'remember' where it left off in calculations.
It goes without saying that each time the fib function is called, eax (the return value) is saved by being pushed onto the stack as n.
Also, it's clearly important to remember each 'old ebp' so that the stack of started functions can safely finish out on their personal stack frames.
I hope this makes things somewhat clearer. I can sense you're the kind of person who really wants to understand how things work, and Assembly language is very good for providing that understanding. I highly recommend you pick up the book "Assembly language Step by Step" by Jeff Duntemann. You can also check out the tutorials "Art of Assembly" and do a search on Google for Dr. Paul Carter's assembly language tutorial. It is very good.
[ 02 August 2001: Message edited by: Niminator ]
sincka
08-02-2001, 01:34 PM
Aaaahhhh... *sigh of relief* :)
Finally, I can understand the damn thing.
Thank you all for helping me out on this subject since I was really going nuts. I guess that I will have to learn Assembly in order to understand how the computer works. Hhmmm... oh well, at least I am one step closer to my goal :p
Thanx again. Later.
TacKat
08-02-2001, 02:37 PM
You don't have to learn assembly to understand how things are executed, but you'll find that once you do learn assembly things like pointers and different call types make perfect sense.
Even if you don't want to program in assembly I highly recommend learning it just for the intellectual understanding.
lazy_cod3R
08-03-2001, 07:22 PM
I was trying to explain to someone how recursion works and they had one hell of a time understanding it that i had no other way to show them except to write the same function under itself 5 times so instead of them followng the recursion on the single recursive function they follow it through multiple identical functions until they understood how it works, then when they finally understood i explained to them how the variables are initialsed for every call of the function because its like calling any other function (where the local vars have no value unless assigned)except in recusrions case its the same function,until they understood how recusion does its thing, try writing the function out many times to see how it works its probably a pretty lame way of doing things but it showed the guys I was explaing this to :)
[ 03 August 2001: Message edited by: lazy_cod3R ]
castlef
08-04-2001, 01:28 AM
heres a quote from the inventor of Pascal, Niklaus Wirth: "In fact, the explanation of the concept of recursive algorithm by such inappropriate examples has been a chief cause of creating widespread apprehension and antipathy toward the use of recursion in programming, and of equating recursion with inefficiency."
debiandude
08-04-2001, 07:36 PM
This is a much better way to do the fib numbers, it does it without recursion. Fib numbers really shouldn't be used to teach recursion. Its just bad.
#include <stdio.h>
#include <math.h>
long double fib(int n);
int main(void) {
int n;
long double ans;
printf("Welcome to the Fib num generator. Enter a num: " );
scanf("%d", );
ans = fib(n);
I thought about it a while, and it seems it would be bad to do this because each recursion launches an additional 2 copies of the fib function, meaning that the number of recursions will be 2 to the x power, with x being the levels of recursion. So with only 4 recursion levels(that is, 4 numbers generated in the sequence), you'd get about 16 calls to the fib function, and your memory usage just starts getting ugly soon after that...
Let me know if I'm dead wrong, just kind of guessing on this one.
[ 05 August 2001: Message edited by: Niminator ]
jemfinch
08-05-2001, 02:43 PM
That's true, although there are tricks to get around it.
Again, anything that can be expressed iteratively can be expressed recursively in the same order, assuming tail recursion optimization (which isn't in all languages -- in fact, most languages don't do it; the ones I know of that do it by definition are Scheme and ML; by convention, Common Lisp also does it.)
(Tail recursion, by the way, is when the last thing the function does is call itself outside of any other context. It can be optimized to a simple loop in most languages (except languages that support non-linear continuations, but that's getting into another bag of worms :D))
A tail recursive version of fib is as follows:
let rec fib_aux a b n =
if n < 2 then
a
else
fib_aux (a+b) a (n-1);;
let fib n = fib_aux 1 1 n;;
Note that the last call of fib_aux is a call to itself, outside of any context (such as the construction of a list or something.) That makes it so that the compiler can optimize that function to a loop, rather than a function call. Underlyingly, the compiler is just changing the value of a, b, and n, and then jumping back to the beginning of the function. It can do that because it knows that it doesn't need to keep the function's old stack frames around.
Note also the way we made fib tail recursive. We stuck an "accumulator" in the arguments. "a" just sticks around accumulating values until the function can return it. That's the standard way to convert an iterative algorithm to recursion: use an accumulator to keep the information you need, instead of just letting the compiler store that information on the stack.
If this was too complicated or uninteresting to you, don't worry about, it's pretty esoteric in the whole realm of computer programming :)
Jeremy
justlinux.com
Copyright Internet.com Inc. All Rights Reserved.