These notes are in-class notes with added information like pictures and diagrams taken from the net. They summarize and display the most important parts of these 3 chapters. They are color-coordinated for ease of learning and structured with enough white space that if/when printed, one can annotate...
Recursion: Solving a problem by breaking it down into smaller, similar problems.
Base Case: A specific condition that stops the recursion and provides a direct
solution. This is the point where the program stops calling itself and returns a
result.
Recursive Programming: Writing methods that call themselves to solve problems
recursively. It can be used as an alternative to iterative
approaches.
Example: Factorial
public int factorial(int num){
if (num==0) {
return 1;
else
return num * factorial(num-1);
}
Using FOR LOOP
public int factorial(int num) {
int result = 1;
for (int i = 1; i <= num; i++) {
result *= i;
}
return result;
}
, Difference between Iterative and Recursive
Both iteration and recursion are based on a control structure:
• Iteration uses a repetition structure, to repeat actions (e.g., for or while loop).
• Recursion uses a selection structure, repeating through method calls (e.g., if-
else statement).
Both involve repetition:
• Iteration explicitly uses a repetition structure.
• Recursion achieves repetition through repeated method calls.
Each also has a termination test:
• Iteration terminates when the loop-continuation condition fails.
• Recursion terminates when a base case is recognized (stops when it reaches
a base case).
Both can occur infinitely:
• An infinite loop occurs with iteration if the loop-continuation test never
becomes false.
• Infinite recursion occurs if the recursion step does not reduce the problem
toward the base case.
Recursion repeatedly invokes the mechanism and overhead of method calls, which
can be costly in terms of both processor time and memory space. [ Recursion,
however, has the added overhead of method calls, which can consume more time
and memory compared to iteration.]
In simpler terms:
Infinite loops or recursion can happen if the termination condition is never met.
- For loops, this means the loop condition never becomes false.
- For recursion, this means the base case is never reached.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Elitish. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.49. You're not tied to anything after your purchase.
