Recursion
little_hacker
horizontal lines and 5 vertical lines intersecting each other. But i'm
confused about how to write a program that uses recursion. Can anyone show
me a program using recursion? Thanks in advance.
Abdulaziz Ghuloum
Did your instructor assign any books or other reading material for the
class? I am sure any book on Scheme has at least one program that uses
recursion.
Aziz,,,
Steve Schafer
wrote:
A program that draws 5 horizontal lines is a program that draws 4
horizontal lines and then draws an additional line.
A program that draws 4 horizontal lines is a program that draws 3
horizontal lines and then draws an additional line.
A program that draws 3 horizontal lines is a program that draws 2
horizontal lines and then draws an additional line.
A program that draws 2 horizontal lines is a program that draws 1
horizontal line and then draws an additional line.
A program that draws 1 horizontal line is a program that draws 0
horizontal lines and then draws an additional line.
A program that draws 0 horizontal lines does nothing at all.
--------
The above depicts the two key aspects of a recursive process:
1) You have to have a recursion rule: We want to know what to do for
case n. Can we derive it from what we have to do for case n - 1?
2) You have to have a "base" case: How do we stop the recursion?
In the above, the recursion rule is simple: Given a program that draws n
lines, we can create a program that draws n + 1 lines by invoking the
program that draws n lines and then drawing one more line.
The base case is simple, too: A program that draws 0 lines ends the
recursion.
--------
I don't want to do your homework for you, so I'll give the solution to a
different recursive problem: Generate a list of all of the powers of 2,
from the nth power down to the 0th power, where n is a parameter that
you pass to a function. So, for example,
(powers-of-two 3)
should return
(8 4 2 1)
while
(powers-of-two 5)
should return
(32 16 8 4 2 1)
and so on. let's look at the list of results for different values of n a
bit more carefully:
n (powers-of-two n)
0 (1)
1 (2 1)
2 (4 2 1)
3 (8 4 2 1)
The recursive nature of the problem is clear: The base case is n = 0,
with a result of (1). The recursion rule is: To get the result for n,
take the first element of the result for n - 1, double it, and then
prepend that value to the result for n - 1.
Here's a direct translation of the above English description into
Scheme:
(define (powers-of-two n)
(if (= n 0)
'(1) ; base case
(cons (* 2 (car (powers-of-two (- n 1))))
(powers-of-two (- n 1))))) ; recursion rule
This could be made more efficient, by computing (powers-of-two (- n 1))
just once and storing the result, but you get the idea. It also isn't
very bulletproof; think about what happens with
(powers-of-two -1)
to see why.
Steve Schafer
Fenestra Technologies Corp.
http://www.fenestra.com/
Theo R.
> Here's a direct translation of the above English description into
> Scheme:
>
> (define (powers-of-two n)
> (if (= n 0)
> '(1) ; base case
> (cons (* 2 (car (powers-of-two (- n 1))))
> (powers-of-two (- n 1))))) ; recursion rule
I tried out a variation -
(define (power-n x)
(define power-x
(lambda (n)
(if (= n 0)
(list 1)
(cons (power x n) (power-x (- n 1)))))))
power is function that gives me the power of x to y
I then defined power-two as
(define (power-two n)
(power-n 2))
Then, I tried to do this
(begin
(display (power-two 5)) (newline)
(display (power-two 8)) (newline)
(display (power-two 2)) (newline)
(display (power-two 0)) (newline))
I have a few problems
1. MIT Scheme loads the file properly but does not display anything
other than saying that the there is no return value.
2. Scheme48 says that there is a syntax error - ill formed definition
for power-x.
It works fine if I just define power-two as
;(define (power-two n)
;(if (= n 0)
;(list 1)
;(cons (power 2 n) (power-two (- n 1)))))
Any ideas?
--
Theo
Steve Schafer
wrote:
>I tried out a variation -
>
>(define (power-n x)
> (define power-x
> (lambda (n)
> (if (= n 0)
> (list 1)
> (cons (power x n) (power-x (- n 1)))))))
>
>power is function that gives me the power of x to y
>I then defined power-two as
>(define (power-two n)
> (power-n 2))
In your definition of power-n, you've given an internal definition (for
power-x), but you've left out the function body:
(define (power-n x)
(define power-x
(lambda (n)
(if (= n 0)
(list 1)
(cons (power x n) (power-x (- n 1))))))
power-x) ; <-- this line
And the syntax of the definition of power-two is a little off:
(define (power-two n)
((power-n 2) n))
Simon Richard Clarkstone
> On Tue, 23 Jan 2007 16:03:33 -0500, "little_hacker" <blac...@aol.com>
> wrote:
>>At school we're making programs using recursion. I have to make 5
>>horizontal lines and 5 vertical lines intersecting each other. But i'm
>>confused about how to write a program that uses recursion. Can anyone show
>>me a program using recursion? Thanks in advance.
>
> A program that draws 5 horizontal lines is a program that draws 4
> horizontal lines and then draws an additional line.
>
> A program that draws 4 horizontal lines is a program that draws 3
> horizontal lines and then draws an additional line.
>
> A program that draws 3 horizontal lines is a program that draws 2
> horizontal lines and then draws an additional line.
>
> A program that draws 2 horizontal lines is a program that draws 1
> horizontal line and then draws an additional line.
>
> A program that draws 1 horizontal line is a program that draws 0
> horizontal lines and then draws an additional line.
>
> A program that draws 0 horizontal lines does nothing at all.
Steve could have make this tail-recursive too, by changing the
definitions to:
"""
A program that draws 5 horizontal lines is a program that draws an
initial horizontal line, then draws 4 horizontal lines.
A program that draws 4 horizontal lines is a program that draws an
initial horizontal line, then draws 3 horizontal lines.
etc.
"""
If the guy wanted to draw 300 lines (plausible) this could make a
difference, as some scheme interpreters cannot handle non-tail recursion
more than 250-or-so deep (As I found out with a factorial program).
--
Simon Richard Clarkstone: s.r.cl?rkst?n?@durham.ac.uk/s?m?n.cl?rkst?n?@
hotmail.com ### "I have a spelling chequer / it came with my PC /
it plainly marks for my revue / Mistake's I cannot sea" ...
by: John Brophy (at: http://www.cfwf.ca/farmj/fjjun96/)