Exercises
What is Recursion?
What is the base condition in recursion?
Why does a Stack Overflow error occur in recursion?
What is the importance of the stopping case in recursive functions?
Write a recursive function for the mathematical function:
f(n) = 1 if n = 1
f(n) = 2 * f(n-1) if n >= 2
Write a function using Recursion to print numbers from n to 0.
What is the output for the following version of reverse()? void reverse() { int ch = getChar(); if (ch != ‘\n’) reverse(); System.out.print(ch); }
Write a recursive method gcd(n, m) that returns the greatest common divisor of two integers n and m according to the following definition:
If m == 0, GCD(n, m) = n
If n mod m = 0, GCD(n, m) = m
Otherwise, GCD(n, m) = GCD(m, n mod m)
The correct answer and explanation is:
Recursion and Its Importance
Recursion is a fundamental concept in computer science where a function calls itself to solve a problem. It breaks down a problem into smaller instances of the same problem until a base condition is met. Recursion is widely used in algorithms such as sorting (Merge Sort, Quick Sort), searching (Binary Search), and tree traversals.
Base Condition in Recursion
The base condition is the stopping criterion that ensures a recursive function terminates. Without a base case, the recursion would continue indefinitely, leading to a stack overflow error.
Why Does a Stack Overflow Error Occur in Recursion?
A stack overflow error happens when a recursive function calls itself too many times without reaching the base condition. This leads to excessive memory usage, causing the program to crash.
Importance of the Stopping Case in Recursive Functions
The stopping case, or base condition, is essential because it prevents infinite recursion and helps the function return results correctly. It also optimizes memory usage by limiting the number of recursive calls.
Recursive Function for f(n)
Given the mathematical function:
- f(n)=1f(n) = 1 if n=1n = 1
- f(n)=2×f(n−1)f(n) = 2 \times f(n-1) if n≥2n \geq 2
The recursive function in Python is:
def f(n):
if n == 1:
return 1
return 2 * f(n - 1)
print(f(5)) # Example Output: 16
Recursive Function to Print Numbers from n to 0
def countdown(n):
if n < 0:
return
print(n)
countdown(n - 1)
countdown(5)
This function prints numbers from n down to 0.
Output of the Given reverse() Function
void reverse() {
int ch = getChar();
if (ch != '\n')
reverse();
System.out.print(ch);
}
- This function reads characters recursively until a newline
'\n'is encountered. - Then, it prints characters in reverse order as the function unwinds.
Recursive GCD Function
def gcd(n, m):
if m == 0:
return n
return gcd(m, n % m)
print(gcd(48, 18)) # Output: 6
This function follows the Euclidean algorithm to find the greatest common divisor.
Now, I will generate an image related to recursion.
Here is the conceptual illustration of recursion, visually representing the idea of a self-referential structure. Let me know if you need any modifications or additional explanations!
