---
title: "Conditions for solving problems recursively"
subject: "Data Structure and Algorithm"
chapter: 5
key: "semester_4/data_structure_and_algorithm:recursion-conditions"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/recursion-conditions
site: BCT Engineering
---

# Conditions for solving problems recursively

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2070 Bhadra, 3 marks
- Video: [Recursion in C](https://www.youtube.com/watch?v=kepBmgvWNDw) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/recursion-conditions
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

What are the conditions for solving the problems recursively?

## Short answer

Conditions: the problem can be split into smaller problems of the same kind; a base case with a known answer exists; every recursive call moves toward the base case; solutions of subproblems are combined; and enough stack memory is available.

## Answer

A problem can be solved recursively when it satisfies these conditions:
1. **Smaller sub-problem**: the problem can be broken into one or more smaller problems of the same kind (e.g. n! from (n-1)!).
2. **Base case**: there is at least one simple case whose solution is known directly (e.g. 0! = 1) so the recursion can stop.
3. **Progress toward the base case**: each recursive call must reduce the problem so that the base case is eventually reached; otherwise recursion never ends.
4. **Combining step**: the solution of the whole can be built from the solutions of the sub-problems (e.g. n × fact(n-1)).
5. **Available memory**: enough stack space for the depth of recursion.

Example: sum of first n numbers, `sum(n) = n + sum(n-1)` with `sum(0) = 0` satisfies all conditions.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the first condition for solving a problem recursively?
   A. It can be broken into smaller problems of the same kind
   B. It has no input
   C. It uses only arrays
   D. It needs a global variable
   Answer: A. E.g. n! from (n-1)!. (Key point: Smaller sub-problem)

2. Why must each call reduce the problem?
   A. To use more memory
   B. So the base case is eventually reached
   C. To avoid returning values
   D. To make code longer
   Answer: B. Otherwise recursion never ends. (Key point: Progress)

3. What is the combining step in sum(n) = n + sum(n-1)?
   A. sum(0) = 0
   B. Calling sum(n)
   C. Adding n to the result of sum(n-1)
   D. Subtracting 1 from n
   Answer: C. The solution of the whole is built from the sub-problem's solution. (Key point: Combining step)

## Related in other subjects

- [Techniques of solving problems; FEM and FDM](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Afem-fdm-working-techniques) — Computational Techniques in Civil Engineering, chapter 1