Explain recursion and give a simple example.

Explain recursion and give a simple example.

• A. Recursion is a loop that repeats until a condition is met.
• B. Recursion is a function calling itself with smaller subproblems until a base case is reached.
• C. Recursion is a data structure like a stack.
• D. Recursion is always more efficient than iteration.

Answer: (B)

Recursion is a way of solving a problem by having a function call itself with a smaller piece of the same problem, and it stops when it reaches a base case that can be answered directly. Each recursive call tackles a smaller subproblem, and when the base case is reached, the results flow back through the chain of calls as they return. A simple example is summing the numbers from 1 to n. If n is 0, you return 0 as the base case. Otherwise you return n plus the sum of 1 through n-1, which is accomplished by calling the same function with n-1. def sum_to(n): if n == 0: return 0 return n + sum_to(n-1) Calling sum_to(4) builds a stack of calls: 4 calls 3, which calls 2, then 1, then 0; 0 returns 0, and the results unwind as 1, 3, 6, 10. The base case is essential to stop the recursion; without it, the function would keep calling itself until the program runs out of stack space. Recursion fits problems that can be divided into similar subproblems, but it isn’t always the most efficient approach because each call adds overhead. An iterative loop can often achieve the same result more quickly, which is why one of the other statements sees recursion as a loop or as inherently more efficient; those descriptions aren’t precise or universally true.