Conditions for solving problems recursively

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.