Review: the recursive problem solving technique

Review: the Recursive problem solving technique (CS170 + CS171 material)

Key to understand recursion:

Do not look at a recursive function as a function that "calls itself" (as many text book teaches)

int fac( int n ) { ... ... return ( n * fac(n-1) ); // Function "calls itself" }

Rather:
Example:

The Recursive problem solving technique (a.k.a.: divide and conquer):

Divide a problem P(n) of size n into a number of smaller porblems of the same type

Conditions for applying recursion:

The original problem P(n) can be solved easily using the solutions for the smaller problems
There are base cases (small problems) of the problem that we can solved easily

The recursive problem solver has the following structure:

solve( n ) { Sol s1, s2, s3, ...; Sol sol; /* ================================================= Take care of the "base cases" seperately (this will stop the "infinite recursion" problem ================================================== */ if ( n == a base_case ) { return ( base_case_solution(n) ); // Base case } /* =================================================== This is the recursive solver =================================================== */ /* --------------------------------------- Solve smaller problems (divide step) --------------------------------------- */ s1 = solve( n-1 ); // s1 = the solution of smaller problem "n-1" s2 = solve( n-2 ); // s2 = the solution of smaller problem "n-2" s3 = solve( n-3 ); // s3 = the solution of smaller problem "n-3" .... /* ---------------------------------------------- Use the solutions for the smaller problems to solve the ORIGINAL problem (conquer step) ----------------------------------------------- */ sol = combine( s1, s2, s3, ..... ); /* ---------------------------- Return the solution... ---------------------------- */ return (sol); }