My head is spinning
Author
I''m trying to get my head around recursion and not having much luck. Can someone point to a really good online tutuorial for recursion??
Sorry no links, but here is an example:
long Factorial(long p_num)
{
if (p_num == 1)
return 1;
else
return p_num * Factorial(p_num - 1);
}
Factorial(5) returns 5*4*3*2*1 = uh, ... 120.
Recursion in general has a stopping point (return 1) and a point where it calls itself again that leads to the stopping point (Factorial(p_num - 1))
Another good example of recursion is tree parsing routines. They call themselves again with the next node to go to, and stop the parse when the next node is NULL.
[edited by - Waverider on August 22, 2002 11:05:52 AM]
long Factorial(long p_num)
{
if (p_num == 1)
return 1;
else
return p_num * Factorial(p_num - 1);
}
Factorial(5) returns 5*4*3*2*1 = uh, ... 120.
Recursion in general has a stopping point (return 1) and a point where it calls itself again that leads to the stopping point (Factorial(p_num - 1))
Another good example of recursion is tree parsing routines. They call themselves again with the next node to go to, and stop the parse when the next node is NULL.
[edited by - Waverider on August 22, 2002 11:05:52 AM]
A recursive method calls itself as long as a stop condition is not true.
The most important with recursive calls are:
* A stop condition.
The algorithm must have a goal.
* Change of input data.
A childinstance should operate on "Data+1/Data-1"
Don't read so much about them. Try them, blow the stack a few times (i know that sounds dirty...) and learn.
Bottomline. A method that calls itself:
This doesn't work since the never ending calls will blow the stack.
function BlowStack;
begin
result BlockStack;
end;
However this will:
function StopAtFive(Value: Integer);
var Val: Integer;
begin
Val := Value + 1;
If Value = 5 then
return;
else
StopAtFive(Val);
end;
[edited by - ekas78 on August 23, 2002 3:49:20 PM]
The most important with recursive calls are:
* A stop condition.
The algorithm must have a goal.
* Change of input data.
A childinstance should operate on "Data+1/Data-1"
Don't read so much about them. Try them, blow the stack a few times (i know that sounds dirty...) and learn.
Bottomline. A method that calls itself:
This doesn't work since the never ending calls will blow the stack.
function BlowStack;
begin
result BlockStack;
end;
However this will:
function StopAtFive(Value: Integer);
var Val: Integer;
begin
Val := Value + 1;
If Value = 5 then
return;
else
StopAtFive(Val);
end;
[edited by - ekas78 on August 23, 2002 3:49:20 PM]
To my understanding, any recursive algorithm can be written iteratively (using a loop). But sometimes they''re just soooooooooooo elegant 
I suggest breaking a few brain-cells and understanding them before thinking iteratively about everything.
umm..my reasoning about all of them written iteratively is Dijkstra''s proof that all programs can be written with goto and coniditional statements. I could be wrong, but I don''t think so
I suggest breaking a few brain-cells and understanding them before thinking iteratively about everything.umm..my reasoning about all of them written iteratively is Dijkstra''s proof that all programs can be written with goto and coniditional statements. I could be wrong, but I don''t think so
There''s no reason a recursive function can''t be written iteratively. All it should take is a bit of work with a stack, and you should be able to rewrite any recursive function. The only question is whether it''s a good thing or not; in some cases recursive functions could turn out being better in the long run (as well as more elegant).
recursion is the same as ITERATIVE exectution, PLUS a stack. To rewrite a recursive algorithm iterativly requires the presence of a stack to keep temporary values in (which recursion uses, but hides in the CALL STACK).
The best USEFUL examples of recursion I can think of are Tree Traversal.
For Example, if you wanted to print out a binary tree, here''s a recursive algorithm to do it, in different orders.
see how cool that is ... you get 3 really simple, really useful functions, all obsurdly easy to understand and debug because you have written them recursively.
Good Luck
The best USEFUL examples of recursion I can think of are Tree Traversal.
For Example, if you wanted to print out a binary tree, here''s a recursive algorithm to do it, in different orders.
void PrintTree_PostOrder(Node *currentNode) { if(Node != 0) { PrintTree_PostOrder(currentNode->LeftChild()); PrintTree_PostOrder(currentNode->RightChild()); currentNode->Print(); } // else is the stop case }void PrintTree_PreOrder(Node *currentNode) { if(Node != 0) { currentNode->Print(); PrintTree_PostOrder(currentNode->LeftChild()); PrintTree_PostOrder(currentNode->RightChild()); } // else is the stop case }void PrintTree_InOrder(Node *currentNode) { if(Node != 0) { PrintTree_PostOrder(currentNode->LeftChild()); currentNode->Print(); PrintTree_PostOrder(currentNode->RightChild()); } // else is the stop case } see how cool that is ... you get 3 really simple, really useful functions, all obsurdly easy to understand and debug because you have written them recursively.
Good Luck
Recursion
Recursion
From: http://www.olympus.net/personal/7seas/recurse.html
[edited by - Like2Byte on August 23, 2002 4:41:21 PM]
[edited by - Like2Byte on August 23, 2002 4:41:51 PM]
int factorial(x){ int prod; if(x <= 0) prod = 1; else prod = x * factorial( x-1 ); return prod;} Recursion
From: http://www.olympus.net/personal/7seas/recurse.html
[edited by - Like2Byte on August 23, 2002 4:41:21 PM]
[edited by - Like2Byte on August 23, 2002 4:41:51 PM]
Xai,
Recursive algos are (often) not that easy to debug.
Your example is straight from CS-101 (so was mine). Which is fairly easy...Have you ever tried to trace a (large) recursive method that branch into other recursive methods(say a rd parser)? That's pure hell right there..
[edited by - ekas78 on August 23, 2002 9:38:04 PM]
Recursive algos are (often) not that easy to debug.
Your example is straight from CS-101 (so was mine). Which is fairly easy...Have you ever tried to trace a (large) recursive method that branch into other recursive methods(say a rd parser)? That's pure hell right there..
[edited by - ekas78 on August 23, 2002 9:38:04 PM]
I''ll try to explain recursion by showing the differences between the iterative and recursion repeative components.
A Repeatitve Process''s Components include:
Initialization: (The repeative structure''s start state)
Iterative - requires a variable that is modified/monitored within the loop
Recursion - requires parameters that are modified by the function
Modification: (Update the repeative structure''s current state)
Iterative - is done inside the loop
Recursion - must be done before the function calls itself
Termination condition: (test the structure''s state for continuing or exiting)
Iterative - can be tested at the start or end of the loop
Recursion - must be tested before any processing
P.S.
First, when using recursion always make sure the termination condition testing is 100%. Secondly, ensure that the function will not call itself too many times because it could blow the stack.
A Repeatitve Process''s Components include:
Initialization: (The repeative structure''s start state)
Iterative - requires a variable that is modified/monitored within the loop
Recursion - requires parameters that are modified by the function
Modification: (Update the repeative structure''s current state)
Iterative - is done inside the loop
Recursion - must be done before the function calls itself
Termination condition: (test the structure''s state for continuing or exiting)
Iterative - can be tested at the start or end of the loop
Recursion - must be tested before any processing
P.S.
First, when using recursion always make sure the termination condition testing is 100%. Secondly, ensure that the function will not call itself too many times because it could blow the stack.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
