Re: need help Recursion and iteration...
[Prev][Next][Index][Thread]
Re: need help Recursion and iteration...
NOTE: This text is best viewed with a fixed pitch font like Courier.
>From ???@??? Sun Dec 20 07:13:29 1998
>Hmm I'm not quite sure, but as I've understood it
>
>recursion is when the next result is dependant on previous results e.g.
>when solving differential equations numerically you need a starting point.
>
>whereas
>
>iteration is calculations dependant on previous results BUT approaching a
>fixed point e.g. like Newton-Raphson zero method you (normally) approach
>one fixed point namely the zero.
>
>If this is not right PLEASE notify me because I need it for an exercise.
>
>Kasper Vibe Grevsen
Well, yes and no...
One of the most important (though initially difficult to explain)
concepts in manipulating data in a program is the distinction between
recursion and iteration. In iteration, the same set of actions might
be carried out a number of times. The procedure is carried out
exactly
the same way the tenth time through as it was the first. The number
of
times the procedure is executed is determined by some factor OUTSIDE
OF
the procedure itself.
In recursion, the procedure is also carried out a number of times.
Here,
however, the execution of each new operation is dependent upon the
result
of the previous one. The number of times a recursive procedure is
executed
is determined by some factor INSIDE OF the procedure itself. Two
conditions
are mandatory for a recursive function:
1- The function must call itself
2- There MUST be a terminating case.
There are a lot of mathematical functions that are defined that way;
they
are called "recurrence functions". A well known exemple is the
Factorial
function. Its exact definition is:
The Factorial of the number N, written as N!, is
undefined if N < 0
1 if N = 0 ; the terminating case.
N * (N-1)! if N > 0 ; the recurrence function itself.
The idea or recursion is not restricted to mathematics. Think of the
song "The twelve days of Chrismas":
On the first day of Chrismas my true love gave to me
A partridge in a pear tree
On the second day of Chrismas my true love gave to me
Two turtle doves
And a partridge in a pear tree
On the third day of Chrismas my true love gave to me
Three french hens
Two turtle doves
And a partridge in a pear tree
( and so on... )
Here each day's gift is made up of two parts: something new plus
what was given the day before. The terminating case is implied to
be the first day.
To illustrate the difference between recursion and iteration, i have
written the factorial function in JavaScript. You can cut the text
below ( at the end of this document )
and save it as "Factorial.htm" to try it in your WEB browser.
The recursive function is:
function factorial(aNumber)
{
aNumber = Math.floor(aNumber);
if (aNumber < 0)
{
return "not a defined quantity";
}
if ((aNumber == 0) || (aNumber == 1))
{
return 1;
}
else return (aNumber * factorial(aNumber - 1));
}
And the iterative version is :
function factorial(aNumber)
{
var i = 0;
var j = 1;
aNumber = Math.floor(aNumber);
if (aNumber < 0)
{
return "not a defined quantity";
}
if ((aNumber == 0) || (aNumber == 1))
{
return 1;
}
else
{
for(i = 2; i < aNumber; i++)
{
j = j * i;
}
return ( j );
}
}
As you can see, the number of iterations is decided outside
of the loop when you type a number in the text box. In the
recursive version, no one, not even the program, knows what
factorial(aNumber - 1) is exactly; it must be computed to go
on. It is in that way that we say that the result of the
loop is dependent of the previous ( in that case, the next )
loop.
This exemple is trivial. Every programmers knows that the
factorial of a number is best computes iteratively. But there
exists some classes of algorythmic problems that can be solved
only through recursion ( graphs and trees ). And in many
cases, recursion leads to programs that are more readable,
easier to debug and faster to write at the cost of using
more memory and taking more time to run.
Hoping that this will help,
Merry Christmas!
{^;^}
/ \ Benont Morrissette, (remove NOSPAM in adress to reply )
------------ Factorial.htm cut here --------------------------------
<html>
<head>
<title>Factorial function in JavaScript</title>
<script language="JavaScript">
<!--
function cls(){
document.Formulaire.AireDeTexte.value = "";
}
function PrintLn(arg){
document.Formulaire.AireDeTexte.value += arg + "\n";
}
function Print(arg){
document.Formulaire.AireDeTexte.value += arg;
}
function factorial(aNumber){
// If the number is not an integer, round it down.
aNumber = Math.floor(aNumber);
// If the number is less than zero, reject it.
if (aNumber < 0) {
return "not a defined quantity";
}
// If the number is 0 or 1, its factorial is 1.
if ((aNumber == 0) || (aNumber == 1)) {
return 1;
}
// Otherwise, recurse until done.
else return (aNumber * factorial(aNumber - 1));
}
function Compute(){
var Iter = (parseInt(document.Formulaire.NUMBER.value));
cls();
Print( "The factorial of ");
PrintLn( Iter );
Print( "is " );
PrintLn( factorial( Iter ) );
}
<!-- -->
</script>
</head>
<body>
<h1>Factorial function in JavaScript</h1><br>
Enter a number in the text box below and press the button to compute
its
factorial. Numbers above 170 will return "infinity" as result.<hr>
<form NAME="Formulaire">
<p>
Enter number here :
<input TYPE="text" SIZE="8" NAME="NUMBER" VALUE="10">
<input type="button" value=" Compute Factorial "
onclick="Compute()">
</p>
<div>
<p>
<textarea NAME="AireDeTexte" ROWS="3" COLS="50"></textarea>
</p>
</div>
</form>
</body>
</html>
------------ end of Factorial.htm cut here
--------------------------------
References: