Lecture 1 Recursion
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.
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.
