Use app×
Join Bloom Tuition
One on One Online Tuition
JEE MAIN 2025 Foundation Course
NEET 2025 Foundation Course
CLASS 12 FOUNDATION COURSE
CLASS 10 FOUNDATION COURSE
CLASS 9 FOUNDATION COURSE
CLASS 8 FOUNDATION COURSE
0 votes
698 views
in Iteration and Recursion by (49.1k points)
closed by

Explain recursive problem solving.

1 Answer

+1 vote
by (54.8k points)
selected by
 
Best answer

To solve a problem recursively, the solver reduces the problem to sub – problems, and calls another instance of the solver, known as sub – solver, to solve the sub – problem. The input size to a sub – problem is smaller than the input size to the original problem. When the solver calls a sub – solver, it is known as recursive call. The magic of recursion allows the solver to assume that the sub – solver (recursive call) outputs the solution to the sub – problem. Then, from the solution to the sub – problem, the solver constructs the solution to the given problem. As the sub – solvers go on reducing the problem into sub – problems of smaller sizes, eventually the sub- problem becomes small enough to be solved directly, without recursion. 

Therefore, a recursive solver has two cases:

1. Base case:

The problem size is small enough to be solved directly. Output the solution. here must be at least one base case.

2. Recursion step:

The problem size is not small enough. Deconstruct the problem into a sub – problem, strictly smaller in size than the given problem. Call a sub – solver to solve the sub problem. Assume that the sub – solver outputs the solution to the sub problem. Construct the solution to the given problem. This outline of recursive problem solving technique is shown below.

Whenever we solve a problem using recursion, we have to ensure these two cases: In the recursion step, the size of the input to the recursive call is strictly smaller than the size of the given input, and there is at least one base case.

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam, ICSE Board Exam, State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

...