,Recursion
Recursion is a method of solving a problem where the solution depends on solutions to smaller instances
of the same problem. So, the tactic is to divide a problem into subproblems of the same type as the
original, solve all the subproblems and combine the results. Recursion is essentially repetition without a
loop.
All recursive methods have the following characteristics:
- One or more base cases are used to stop recursion (a base case is the simplest case)
- Every recursive call reduces the original problem, bringing it increasingly closer to a base case
until it becomes that case.
Let’s consider a simple problem of printing a message for n times. You can break the problem into two
subproblems: one is to print the message one time and the other is to print the message for n-1 times.
The second problem is the same as the original problem with a smaller size. The base case for the
problem is n==0. You can solve this problem using recursion as follows:
nPrintln(“Welcome”, 5);
public static void nPrintln(String message, int times) {
if (times >= 1) {
System.out.println(message);
nPrintln(message, times - 1);
} // The base case is times == 0
}
Recursion bears substantial overhead. Each time the program calls a method, the system must assign
space for all the method’s local variables and parameters. This can consume considerable memory and
requires extra time to manage the additional space.
Recursion is good for solving the problems that are inherently recursive
2
, The big O notation
Most algorithms transform input object into output object where the running time typically grows with
the input size. The average case time is difficult to determine, so we focus on the worst-case running
time. The worst-case running time is easier to analyze and is crucial to applications such as games, finance
and robotics
Experimental studies:
- Write a program implementing the algorithm
- Run the program with inputs of varying size and composition
- Use a method like System.currentTimeMillis() to get an accurate measure of the actual running
time
- Plot the results
Limitations of Experiments
- It is necessary to implement the algorithm, which may be difficult
- Results may not be indicative of the running time on other inputs which are not included in the
experiment
- To compare two algorithms, the same hardware and software environments must be used
Theoretical Analysis
- Uses a high-level description of the algorithm instead of an implementation (pseudo code)
- Characterizes running time as a function of the input size, n.
- Considers all possible inputs
- Allows us to evaluate the speed of an algorithm independent of the hardware/software
Pseudocode
- High-level description of an algorithm
- More structured than English prose, but less detailed than a program
- Preferred notation for describing algorithms
- Hides program design issues
- Example: find max element of an array:
Algorithm arrayMax(A, n)
Input array A of n integers
Output maximum element of A
currentMax A[0]
for i 1 to n − 1 do
if A[i] currentMax then
currentMax A[i]
return currentMax
3
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper marnickscholten. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €3,49. Je zit daarna nergens aan vast.