Recursion is a programming technique where a function calls itself directly or indirectly. This creates a loop-like structure, but instead of using explicit iteration control, recursion relies on function calls to repeat the process.
Recursion vs. Iteration
Feature
Recursion
Iteration
Control flow
Function calls
Looping constructs (e.g., for, while)
Stack usage
Function calls create a stack frame for each recursive call.
Iteration uses a loop counter or condition.
Clarity
Can sometimes be more intuitive for certain problems.
Often more straightforward for simple tasks.
Efficiency
Can be less efficient due to function call overhead.
Can be more efficient for certain problems.
Tail-call optimization
Some compilers can optimize tail-recursive functions.
Not applicable to iteration.
Memory usage
Can consume more memory due to the stack frames created by function calls.
Generally more memory-efficient.
Complexity
Can be more complex to understand and debug.
Often easier to understand and debug.
Problem domains
Well-suited for problems that can be broken down into smaller, similar subproblems.
More suitable for problems that involve a fixed number of repetitions.
Types of Recursion
Direct recursion: A function calls itself directly.
Indirect recursion: A function calls another function, which eventually calls the original function.
Tail recursion: The recursive call is the last operation performed within the function. This can be optimized by some compilers to avoid unnecessary stack frames.
Critique of Recursion
Efficiency: Recursion can be less efficient than iteration due to function call overhead and potential stack overflow.
Clarity: While recursion can be elegant for certain problems, it can also make code harder to understand, especially for complex recursive structures.
Stack overflow: Deeply nested recursive calls can lead to stack overflow errors, especially if the recursion is not properly bounded.
Memory usage: Recursion can consume more memory due to the stack frames created by function calls.
Debugging: Recursive functions can be more difficult to debug due to the multiple function calls and the potential for infinite loops.
Performance: Recursive functions can be less performant than iterative solutions for certain problems, especially when dealing with large datasets.
Laws of Recursion
Base case: A recursion must have a base case that terminates the recursion.
Recursive case: The recursive case should make progress towards the base case.
Correctness: The recursive case should be correct for all valid inputs.
Efficiency: The recursive case should be efficient, avoiding unnecessary computations.
Clarity: Recursive functions should be well-structured and easy to understand.
Boundedness: The recursion should be bounded to prevent infinite loops or stack overflows.
C++ RECURSIVE ALGORITHMS
FACTORIAL:
The factorial of a non-negative integer n: The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers less than or equal to n.
Example: For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.
int factorial(int n) {
if (n == 0) {
return 1; // Base case
} else {
return n * factorial(n - 1); // Recursive case
}
}
TOWERS OF HANOI:
A classic puzzle: A classic puzzle involving three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts: The puzzle starts with all the disks stacked in ascending order of size on one rod, the smallest at the top.
The objective: The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
Only one disk: Only one disk can be moved at a time.
Each move: Each move consists of taking the uppermost disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
No disk: No disk may be placed on top of a smaller disk.
void towersOfHanoi(int n, char source, char destination, char auxiliary) {
if (n == 1) {
cout << "Move disk 1 from " << source << " to " << destination << endl;
return;
}
towersOfHanoi(n - 1, source, auxiliary, destination);
cout << "Move disk " << n << " from " << source << " to " << destination << endl;
towersOfHanoi(n - 1, auxiliary, destination, source);
}
Binary search:
An efficient algorithm: An efficient algorithm to find a specific value within a sorted array.
It works by: It works by repeatedly dividing the search interval in half.
In each step: In each step, the algorithm compares the target value with the middle element of the current interval.
If the target value: If the target value is equal to the middle element, the search is successful.
If the target value: If the target value is less than the middle element, the search continues in the lower half of the interval.
If the target value: If the target value is greater than the middle element, the search continues in the upper half of the interval.
The process repeats: The process repeats until the target value is found or the interval becomes empty, indicating that the target value is not present in the array.
int binarySearch(int arr[], int left, int right, int x) {
if (right >= left) {
int mid = left + (right - left) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, left, mid - 1, x);
return binarySearch(arr, mid + 1, right, x);
}
return -1;
}
Fibonacci sequence:
A series of numbers: A series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1.
The sequence begins: The sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Fibonacci numbers: Fibonacci numbers appear in various mathematical and natural phenomena, such as the branching of trees, the arrangement of leaves on a stem, and the spiral patterns of shells.
