What is recursion?
Recursion describes the ability of a routine to call itself. This means a recursive routine is defined in terms of itself.
Recursion is very powerful and often results in a very elegant solution to a problem. However, iterative solutions usually make more efficient use of computer time and memory space.
Recursive routine: a routine defined in terms of itself.
General cause: the solution in terms on itself for a value n.
Base case: a value that has a solution which does not involve any reference to the general case solution.
The mechanism of recursive routines:
Recursion works only if the routine is called with the current value or values passed as parameters. It would not works with global variables.
Each time a routine is called, a special area of main memory, called the stack, is used. There the return address is stored as well as the contents of registers. Any local variables and the routine's parameters are also allocated space on stacks. The locations in the stack area used to store the values referring to one invocation of a routine is known as a stack frame. When a routine ends, control normally passes to the sotred return address and its stack frame is removed from the stack.
If many recursive calls are made, the stack space could run out. This is known as stack overflow. For example, if the above function Factorial1 were called with a parameter of 0, recursive calls would not terminate normally as the base case of 1 would never be reached. Eventually stack overflow would occur. Because of the stack overheads, recursive algorithms may not be as sufficient as iterative solutions.
STACK FRAME: the locations in the stack area used to store the values referring to one innovation of a routine.
No comments:
Post a Comment