How recursive functions work in a computer program?

I know how to make a recursive funtions but when I trace one it just do not make sense how the computer program language make it work. Seem like magic.


TIA for your answers

How recursive functions work in a computer program?
Recursive functions, work like a sort of loop.





In most loops, you have a variable (itemwalker in the case of lists/collections) which is increased at every loop, until certain condition(s) is met.





Recursive functions (i.e. recurrent functions) call themselves with different variables, until a certain condition is met.





eg. sum for the first 10 numbers using a for loop


sum = 0;


for(i=0; i%26lt;10; i++)


{


sum +=i;


}








sum of first 10 numbers using a recurrent function





int Sum(currentValue, endValue)


{


if (currentValue%26lt;endValue)


{


return currentValue+Sum(currentValue+1,endValue...


}


}





in the main() function, you then call the function as


value = Sum(0,10);





--------------


How the second example work:


currentValue = 0


endValue = 3





I changed the end value, so I don't have to write so much.





0%26lt;3 (true)


Sum(0,3) = 0 + Sum(0+1,3)





So now we have to compute Sum(1,3)





currentValue =1


endValue = 3





1%26lt;3(true)


Sum(1,3) = 1+ Sum(2,3)





now we compute Sum(2,3)





currentValue = 2


endValue = 3





2%26lt;3(true)


Sum(2,3) = 2+Sum(3,3);





now we compute Sum(3,3)


currentValue = 3


endValue = 3





3%26lt;3 (false)


so we stop here. There is no Sum(3,3)





So Sum(2,3) = 2;


Sum(1,3) = 1+Sum(2,3) = 1+ 2 = 3


Sum(0,3) = 0 +Sum(1,2) = 0+3 = 3


value = Sum(0,3) = 3.





Note, it's very important to specify an ending condition. The program stores the temporary values of Sum(1,3) and Sum(2,3) in a memory zone called the "heap", which has the structure of a stack. But this stack is limited. If you forget to mention the ending condition, the program will keep adding value to the "heap" stack which will eventually run out of storage space. And at that moment your program will crash.





The general error message in this case is "stack overflow error"... or at least it is in Pascal.





I hope I explained it clear enough.
Reply:Not sure how to explain it without being visual but this article might help.


"" After all, what is a recursive method really doing under the hood but implicitly making use of the call stack""





This might break it down explaining how the call to the function gets put on the actual computer stack and when the last call is there, all gets popped off.





http://www.doc.ic.ac.uk/~wjk/C++Intro/Ro...





PS. I never liked recursion and seem to still to this day, screw up the last pop from the stack :-)
Reply:LOL it's neither magic nor black art.





A recursive function is simply a function that calls itself. Using recursion, a complex problem is split into its single simplest case. The recursive function only knows how to solve that simplest case.





The recursive functions solve the problem in a method much identical to their real-life solutions.





Recursive functions are the best choice when performance is an issue.





The computer achieves this through using a portion of the memory called "stack"





The alternative is to use iteration.





Hope this helps.
Reply:Same as calling any function, all the local variables are pushed on to a stack when a new function is called, and then popped back off the stack when the function is exited.


You can only recursively call a function until you run out of stack space, which is why you get a "stack overflow" if you attempt infinite recursion