 | | A recursion question/test...
|
|
Hi, With all the discussion on understanding recursion and such for programmers I thought I'd share a little problem I find enlightening.... Describe as simple a recursive algorithm as possible for summing the first n numbers. ___...___ Three step (...) (25 years ago, 12-May-99, to lugnet.robotics)
|
| |
| | Re: A recursion question/test...
|
|
(...) d'oh. my ($n)=@ARGV; my $result=$n; $result += $n while($n--); print $result."\n"; What a difference a compile makes... but it's still not very recursive. I'll be interested in seeing your answer. Aloha, JR - - - - - - - - - - JR Conlin (...) (25 years ago, 12-May-99, to lugnet.robotics)
|
| |
| | Re: A recursion question/test...
|
|
Jim Choate poses the problem: (...) What other than sum(n) = n + sum(n-1) (with proper termination conditions, of course - sum(1) = 1). Ralph deal@kzoo.edu -- Did you check the web site first?: (URL) (25 years ago, 12-May-99, to lugnet.robotics)
|
| |
| | Re: A recursion question/test...
|
|
It should be pointed out that the problem of summing the first n natural numbers is isomorphic to that of finding the factorial of n. Compare these two functions FUNCTION sum(n: natural): natural = IF n = 0 THEN 0 ELSE n + sum(n - 1) FUNCTION fac(n: (...) (25 years ago, 12-May-99, to lugnet.robotics)
|
| |
| | Re: A recursion question/test... (correction)
|
|
Whoops! I typed the last two lines with the two aggregate operators interchanged! Obviously they should have read FUNCTION sum(n: natural): natural = SUM [0..n] FUNCTION fac(n: natural): natural = PRODUCT [1..n] Malcolm -- Did you check the web site (...) (25 years ago, 12-May-99, to lugnet.robotics)
|
| |
| | Re: A recursion question/test...
|
|
It should be pointed out that the problem of summing the first n natural numbers is isomorphic to that of finding the factorial of n. Compare these two functions FUNCTION sum(n: natural): natural = IF n = 0 THEN 0 ELSE n + sum(n - 1) FUNCTION fac(n: (...) (25 years ago, 12-May-99, to lugnet.robotics)
|
| |
| | Re: A recursion question/test...
|
|
(...) int sum(int n) { return n*(n-1)/2; } A degenerate recursive algorithm, of course. Cheers, Ben. -- (URL) grandfather once told me that there are two kinds of people: those who work and those who take the credit. He told me to try to be in the (...) (25 years ago, 12-May-99, to lugnet.robotics)
|
