27087 total geeks with 3528 solutions
Recent challengers:
 Welcome, you are an anonymous user! [register] [login] Get a yourname@osix.net email address 

Articles

GEEK

User's box
Username:
Password:

Forgot password?
New account

Shoutbox
sdchristebrad
<strong><a href="http:/ /www.columbi a-sportswear -outlet.com/ ">columbia jackets outlet</a></ strong> <str ong><a href="http:/ /www.columbi a-sportswear -outlet.com/ ">columbia sportwear outlet</a></ strong> <br> <strong><a href="http:/ /www.columbi a-sportswear -outle
sdchristebrad
[b][url=http ://www.asics onsale.com/a sics-womens- running-shoe s-c-11.html] asics w<strong><a href="http:/ /www.asicson sale.com/asi cs-womens-ru nning-shoes- c-11.html">a sics women's running shoes outlet</a></ strong> <br> <strong><a href="http:/ /www.asicson sale.c
sdchristebrad
<strong><a href="http:/ /www.asicson sale.com/">a sics running shoes</a></s trong> <br> <strong><a href="http:/ /www.asicson sale.com/">a sics running shoes</a></s trong> <br> <strong><a href="http:/ /www.asicson sale.com/">a sics gel kayano 20</a></stro ng> <br> <br
sdchristebrad
[b][url=http ://jpguccise llwellforu.c om/]gucci outlet[/url] [/b] [b][url =http://jpgu ccisellwellf oru.com/]dis count gucci handbags[/ur l][/b] [b][url=http ://jpguccise llwellforu.c om/]gucci on sale[/url][/ b] http://www.c heapjerseysp opular.com/ cheap nfl
sdchristebrad
[b][url=http ://www.santo rinihostels. com/nbspnbsp nbspnbspmens -apex-bionic -jackets-c-3 .html]north face men's apex bionic jacket[/url] [/b] [b][url=http ://www.santo rinihostels. com/nbspnbsp nbspnbspmens -apex-bionic -jackets-c-3 .html]new north face men's apex bi

Donate
Donate and help us fund new challenges
Donate!
Due Date: Oct 31
October Goal: $40.00
Gross: $0.00
Net Balance: $0.00
Left to go: $40.00
Contributors


News Feeds
The Register
Google absorbs
Oxford Uni boffins
in artificial
intelligence boost
quest
Something about
this really STINKS:
Rosetta probe
shoves nose under
comet"s tail
Rackspace launches
big red rack eater
Adorkable overshare
of words like
photobomb in this
year"s dictionaries
MAVEN snaps
eight-bit SPACE
INVADER
"Careful management
of headcount" for
Juniper after tepid
quarter
Boffins want to put
Quanta in
containers, after
docking
Yahoo!
Timestamps!
Now!
Block!
Facebook!
Email!
What does beating a
dead horse look
like? Look no
further than the
US TV giants vs
Samsung gets
virtual with tiny
S5 upgrade and
goggle grab
Slashdot
NY Doctor Recently
Back From West
Africa Tests
Positive For Ebola
Tracking a Bitcoin
Thief
How Sony, Intel,
and Unix Made
Apple"s Mac a PC
Competitor
SMART Begins Live
Public Robocar
Tests In Singapore
Microsoft Exec
Opens Up About
Research Lab
Closure, Layoffs
Tech Firm Fined For
Paying Imported
Workers $1.21 Per
Hour
Mark Zuckerberg
Speaks Mandarin At
Tsinghua University
In Beijing
Assange: Google Is
Not What It Seems
Leaked Documents
Reveal
Behind-the-Scenes
Ebola Vaccine
Issues
Ubuntu 14.10
Released With
Ambitious Name, But
Small Changes
Article viewer

Simple Recursion in Scheme



Written by:rae
Published by:SAJChurchey
Published on:2008-11-21 06:07:51
Topic:Common Lisp
Search OSI about Common Lisp.More articles by rae.
 viewed 14648 times send this article printer friendly

Digg this!
    Rate this article :
Understanding recursion and how to implement it to solve problems using classical examples in functional programming.

Recursion is a term used to describe a function calling itself. It is an important concept in programming and doubly so in Lisp and its dialects. To understand recursion, we turn to Scheme - a minimalistic dialect of Lisp. Since this article assumes basic familiarity with Lisp/Scheme syntax, we'll directly jump into looking at our first code.

(define (sum-of-list my-list)
  (cond
    [(empty? my-list) 0]
    [else (+ (first my-list) (sum-of-list (rest my-list)))]))


The above function sum-of-list consumes a list of numbers and produces an output which is the sum of all numbers in the list. Thus,

(sum-of-list '(1 34 5)) => 40


Note that in the above call, we use list abbreviations using the quoted syntax instead of using the cons syntax.

Dissecting sum-of-list we see that it defines a conditional where the output of an empty list, i.e. '() would evaluate to 0. This makes sense because giving it an input of a list with no elements would mean that the sum of the numbers of this list would be 0.

The interesting part comes in the else part of the conditional. If the list is non-empty like in our case of (1 34 5), the list is broken up into two - an atomic value consisting of the first element of the list extracted by the first operator, and the second part is again a list consisting of everything but the first element of the list in question. This is done using the rest operator.

Note that the first and rest operators are the Scheme equivalents of car and cdr of Lisp.

The operation that is being carried out here is addition since we want the sum of the elements of the list. The first atomic element is to be added to the resultant of (sum-of-list (rest my-list)) which is by our definition a recursive call. Note that the same procedure is being called again without the first element. So, after the first pass, the operation which will be called will be



(sum-of-list '(34 5))




This function call will then in turn go through the same process, each time splitting the list into its first element and the rest of the list till it splits the list into its last element and an empty list, thereby satisfying the first conditional and returning 0. These results are then added up starting from 0 to the first element of the list in reverse order. This process in the end would return us the summation of the list in question, i.e. 40.


We now look at another problem which is commonly solved by recursion - computing the factorial of a number. Here is a recursive Scheme program for the same using the lambda procedure.



(define factorial
  (lambda (n)
  (if (= n 0) 1
  (* n (factorial (- n 1))))))



In this example, using recursion we're reducing the problem to a simpler one by recursively calculating the factorial of n - 1. For the case where n equals to 0, we have a base case condition where the problem cannot be simplified further and the recursion stops. This is the same as the case of an empty list in the first example we saw while calculating the sum of a list of numbers.

Since Scheme and other purely functional languages don't give us classical iterative approaches like looping, the most natural way to solve such classes of problems boils down to recursion, where a problem is simplified into smaller pieces and a simple operation like addition or multiplication (the above two examples respectively) and a base case is identified. This base case then has a trivial solution which allows us to build a solution to the problem at hand bottom-up.

For further reference on recursion in Scheme, How to Design Programs by Felleisen et al and Concrete Abstractions: An introduction to computer science using Scheme by Hailperin et al are excellent books.

Written by Rae

Did you like this article? There are hundreds more.

Comments:
Anonymous
2011-06-07 16:48:31
You forgot to mention that even if a procedure is recursive, its generated process might be iterative (tail calls).
Anonymously add a comment: (or register here)
(registration is really fast and we send you no spam)
BB Code is enabled.
Captcha Number:



     
Your Ad Here
 
Copyright Open Source Institute, 2006