Cadence® system design and verification solutions, integrated under our System Development Suite, provide the simulation, acceleration, emulation, and management capabilities.
Verification Suite Related Products A-Z
Cadence® digital design and signoff solutions provide a fast path to design closure and better predictability, helping you meet your power, performance, and area (PPA) targets.
Full-Flow Digital Solution Related Products A-Z
Cadence® custom, analog, and RF design solutions can help you save time by automating many routine tasks, from block-level and mixed-signal simulation to routing and library characterization.
Overview Related Products A-Z
Driving efficiency and accuracy in advanced packaging, system planning, and multi-fabric interoperability, Cadence® package implementation products deliver the automation and accuracy.
Cadence® PCB design solutions enable shorter, more predictable design cycles with greater integration of component design and system-level simulation for a constraint-driven flow.
An open IP platform for you to customize your app-driven SoC design.
Comprehensive solutions and methodologies.
Helping you meet your broader business goals.
A global customer support infrastructure with around-the-clock help.
24/7 Support - Cadence Online Support
Locate the latest software updates, service request, technical documentation, solutions and more in your personalized environment.
Cadence offers various software services for download. This page describes our offerings, including the Allegro FREE Physical Viewer.
The Cadence Academic Network helps build strong relationships between academia and industry, and promotes the proliferation of leading-edge technologies and methodologies at universities renowned for their engineering and design excellence.
Participate in CDNLive
A huge knowledge exchange platform for academia to network with industry. We are looking for academic speakers to talk about their research to the industry attendees at the Academic Track at CDNLive EMEA and Silicon Valley.
Come & Meet Us @ Events
A huge knowledge exchange platform for academia. We are looking for academic speakers to talk about their research to industry attendees.
Americas University Software Program
Join the 250+ qualified Americas member universities who have already incorporated Cadence EDA software into their classrooms and academic research projects.
EMEA University Software Program
In EMEA, Cadence works with EUROPRACTICE to ensure cost-effective availability of our extensive electronic design automation (EDA) tools for non-commercial activities.
Apply Now For Jobs
If you are a recent college graduate or a student looking for internship. Visit our exclusive job search page for interns and recent college graduate jobs.
Cadence is a Great Place to do great work
Learn more about our internship program and visit our careers page to do meaningful work and make a great impact.
Get the most out of your investment in Cadence technologies through a wide range of training offerings.
Overview All Courses Asia Pacific EMEANorth America
Instructor-led training [ILT] are live classes that are offered in our state-of-the-art classrooms at our worldwide training centers, at your site, or as a Virtual classroom.
Online Training is delivered over the web to let you proceed at your own pace, anytime and anywhere.
Exchange ideas, news, technical information, and best practices.
The community is open to everyone, and to provide the most value, we require participants to follow our Community Guidelines that facilitate a quality exchange of ideas and information.
It's not all about the technlogy. Here we exchange ideas on the Cadence Academic Network and other subjects of general interest.
Cadence is a leading provider of system design tools, software, IP, and services.
Get email delivery of the Cadence blog featured here
Recall the sumlist_1a function
In a previous posting the function sumlist_1a was defined.
(defun sumlist_1a (numbers)
(let ((sum 0))
(foreach number numbers
sum = sum + number)
Describing this algorithm in words, we see that it does not express the mathematical relationship very well, but it does describe how a Von Neumann machine would perform the calculation.
The following implementation of sumlist_3a is an example of simple recursion.
(defun sumlist_3a (numbers)
(plus (car numbers)
(sumlist_3a (cdr numbers)))
Expressing this algorithm in words, you can see that it is more elegant than sumlist_1a as the code actually expresses a mathematical relationship.
An advantage of recursive functions such as sumlist_3a is that they are elegant. They often require less code because there is no need to maintain state; e.g., there is no accumulator variable, and no variables are modified during the evaluation of the function.
The sumlist_3b function is a tail recursive version of sumlist_3a.
(defun sumlist_3b (numbers)
(labels ((sum (sum_so_far rest)
(sum (plus (car rest) sum_so_far)
(sum 0 numbers)))
An obvious drawback of this type of recursive function is that it is more difficult for the human to read than simple recursion.
Tail recursion is a technique which can be used to enable recursive function to require no more stack space than iterative functions. There is a pretty clear explanation on Wikipedia.
The main difference, computation-wise, between sumlist_3a and sumlist_3b is the following. In sumlist_3a the final computation the function does is to call the plus function. For example the top level call to sumlist_3a with (1 2 3 4 5 6 7) must completely finish processing (2 3 4 5 6 7) before it can add the 1--the call to (plus 1 ...) cannot occur before the recursive call to sumlist_3a returns.
(1 2 3 4 5 6 7)
(2 3 4 5 6 7)
(plus 1 ...)
In sumlist_3b, on the other hand, the computation order is reversed. In the local function, sum, the (plus 1 ...) happens first. That partial sum is passed as the sum_so_far parameter. The final thing the local function does is call itself recursively. There is no pending operating waiting for the recursive call to return.
We'll talk more about why this is important in an upcoming posting of SKILL for the Skilled -- Many Ways to Sum a List.
If we call sumlist_1a, sumlist_3a, and sumlist_3b on some examples we see that they return the same thing.
(sumlist_1a '(1 2 3 4 5 6 7))
(sumlist_3a '(1 2 3 4 5 6 7))
(sumlist_3b '(1 2 3 4 5 6 7))
That the computation order of sumlist_3a and sumlist_3b are opposite can be seen by tracing the plus function.
(sumlist_3a '(1 2 3 4 5))
||||||(5 + 0)
||||||plus --> 5
|||||(4 + 5)
|||||plus --> 9
||||(3 + 9)
||||plus --> 12
|||(2 + 12)
|||plus --> 14
||(1 + 14)
||plus --> 15
(sumlist_3b '(1 2 3 4 5))
||||(1 + 0)
||||plus --> 1
|||||(2 + 1)
|||||plus --> 3
||||||(3 + 3)
||||||plus --> 6
|||||||(4 + 6)
|||||||plus --> 10
||||||||(5 + 10)
||||||||plus --> 15
Looking at the trace output, we see that sumlist_3a calls plus with first argument being first 5, then 4, 3, 2, and finally 1. However, sumlist_3b, plus is called first with first argument being 1, then with 2, 3, 4, and finally with 5. Since integer addition is commutative, associative, and side effect free, both algorithms give the same result.
This difference in the two computation models might be important in some situations if some function other than plus is used. For example, if a function with side effects is used, you might find that the side-effects happen in a different order.
For example, replacing the 0 with nil, replacing the plus function with cons, and renaming the local function from sum to rev we have two different and useful functions: a list-copy function and a list-reverse function.
(defun copy_3e (numbers)
(cons (car numbers)
(copy_3e (cdr numbers)))
(defun reverse_3f (numbers)
(labels ((rev (list_so_far rest)
(rev (cons (car rest) list_so_far)
(rev nil numbers)))
Testing these functions we see the following results:
(copy_3e '(1 2 3 4 5))
==>(1 2 3 4 5)
(reverse_3f '(1 2 3 4 5))
==>(5 4 3 2 1)
In the paragraphs above we looked at two different types of recursive functions. The two techniques usually give compatible results. However, depending on the application one technique may be preferable because of computation order or order of side effects.
I've alluded several times to the issue that these recursive functions fail for very long lists. In the next post we'll look at some ways of dealing with this issue.