Local variables and formal parameters are stored on the stack. Recursion is the process of calling a function from within itself, saving local variables and formal parameters. Since the stack is a recursive last-in-first-out data structure, the best place to place variables for each step is on the stack.
The classic example is N Factorial...
int nfact (int n) if (n == 2) return n else return nfact (n - 1);
This example only has one formal parameter. If you called it as nfact(10), by the time n reached 2 there would be 9 return addresses and 9 formal parameters on the stack, and nfact() would have been called 9 times. At that point, the stack unwinds due to the return n statement, and the final result is 3628800.
A simplified picture of the stack at n==2 would look like ...
10
return address of caller
9
return address in nfact
8
return address in nfact
7
return address in nfact
6
return address in nfact
5
return address in nfact
4
return address in nfact
3
return address in nfact
2
return address in nfact
More complex code could easily create and manipulate local variables, so long as they were on the stack. Each recursive instance, then, would be properly isolated from its parent and child, and they would not interfere with each other.
yes
Sure, recursion can always be substituted with using a stack.
Read the part in your programming manual/text book about recursion. The short answer while easy does not tell you anything about the power or dangers of recursion. It is the power and dangers of recursion that is important because once understood you can use recursion to good effect without running out of stack space.
Yes. It is possible to provide a solution to the diamond-square algorithm using Java and recursion.
These terms are found in Recursion.1.Base Case:it is the case in recursion where the answer is known,or we can say the termination condition for a recursion to unwind back.For example to find Factorial of num using recursion: int Fact(int num){ if(num==1 num==0)//base casereturn 1;else // recursive case: return num*Fact(num-1);} 2.Recursive case:It is the case whcih brings us to the closer answer. Run Time Stack:It is a system stack us to save the frame stack of a function every recursion or every call.This frame stack consists of the return address,local variables and return value if any. Tail Recursion:The case where the function consist of single recursive call and it is the last statement to be executed.A tail Recursion can be replace by iteration. The above function consists of tail recursion case.where as the below function does not. void binary(int start,int end,int el){int mid;if(end>start){mid=(start+end)/2;if(el==ar[mid])return mid;else{if(el>ar[mid])binary(mid+1,end,ele);elsebinary(start,mid-11,ele);
yes
Sure, recursion can always be substituted with using a stack.
Read the part in your programming manual/text book about recursion. The short answer while easy does not tell you anything about the power or dangers of recursion. It is the power and dangers of recursion that is important because once understood you can use recursion to good effect without running out of stack space.
Stack is not a way to perform quicksort, it is a tool used to implement recursion.
Read the part in your programming manual/text book about recursion. The short answer while easy does not tell you anything about the power or dangers of recursion. It is the power and dangers of recursion that is important because once understood you can use recursion to good effect without running out of stack space.
Heap is a data-structure, it cannot implement anything. On the other hand, it is true that: 1. Recursive routines might use heap. 2. You can use dynamic memory allocation (heap), to implement a stack; and use the stack to implement recursion.
Yes. It is possible to provide a solution to the diamond-square algorithm using Java and recursion.
These terms are found in Recursion.1.Base Case:it is the case in recursion where the answer is known,or we can say the termination condition for a recursion to unwind back.For example to find Factorial of num using recursion: int Fact(int num){ if(num==1 num==0)//base casereturn 1;else // recursive case: return num*Fact(num-1);} 2.Recursive case:It is the case whcih brings us to the closer answer. Run Time Stack:It is a system stack us to save the frame stack of a function every recursion or every call.This frame stack consists of the return address,local variables and return value if any. Tail Recursion:The case where the function consist of single recursive call and it is the last statement to be executed.A tail Recursion can be replace by iteration. The above function consists of tail recursion case.where as the below function does not. void binary(int start,int end,int el){int mid;if(end>start){mid=(start+end)/2;if(el==ar[mid])return mid;else{if(el>ar[mid])binary(mid+1,end,ele);elsebinary(start,mid-11,ele);
You overcome limitations of the stack in polygon filling, or in any other algorithm, far that matter, but using an iterative technique, rather than a recursive technique. Recursion is quite useful, and can simplify algorithm design. Polygon filling, however, is a class of algorithm can potentially have a very deep recursion depth. This causes stress on the stack, hence the need for iteration.
There is no inherent relationship between the two. It's possible to implement a stack using an array to store date, but that's about it.
Recursion is what it's called when a function calls itself. When a function calls itself immediately before returning, it's called tail recursion. Tail recursion can be more efficiently written as iteration. In fact a good compiler will recognize tail recursion and compile it as iteration. There is no such thing as left or right recursion in C programming.
Recursive procedures are huge memory hogs. Also, they're a nightmare to debug. Finally, it's pretty rare to find an application that actually needs recursion as opposed to a simpler, more friendly methodolgy.