Master Optimal Algorithms: Recursion, Greedy, Divide-Conquer, DP & Backtracking

Optimal Solution Algorithms Overview

In the real world we constantly seek higher efficiency—whether improving project schedules, finding optimal routing, or maximizing profit. This article introduces the main algorithmic ideas for obtaining optimal solutions.

Recursion

Recursion is a programming technique where a function calls itself to break a large problem into smaller, similar sub‑problems. A recursive solution needs a base case, a forward step, and a return step. When the base condition is not met, the function proceeds forward; when it is met, it returns.

Note: Recursion must have a clear termination condition (the recursive exit).

Greedy Algorithm

A greedy algorithm makes the locally optimal choice at each step, hoping to reach a global optimum without exploring all possibilities. It works well when the problem satisfies the greedy‑choice property and optimal‑substructure, but it may fail for many problems.

Key points:

Choose a measure (metric) that guides the selection.

Ensure the chosen metric leads to a feasible solution.

Prove that the greedy choice yields an optimal solution.

Divide and Conquer

Divide‑and‑conquer splits a complex problem into two or more independent sub‑problems, solves each recursively, and merges the results. Typical characteristics:

The problem size becomes easy to solve after sufficient reduction.

The problem exhibits optimal‑substructure.

Sub‑problem solutions can be combined.

Sub‑problems are independent.

Dynamic Programming

Dynamic programming solves optimization problems with overlapping sub‑problems by storing intermediate results. It follows four steps: define stages, define states, write state‑transition equations, and set boundary conditions. DP is widely used for shortest‑path, knapsack, coin‑change, and many other problems.

Backtracking

Backtracking is a depth‑first search of the solution space tree. It makes a choice, proceeds recursively, and if a dead end is reached it backtracks to try another choice. It is used for permutation generation, N‑Queens, Sudoku, and similar combinatorial problems.

Branch and Bound

Branch‑and‑bound also explores the solution‑space tree but uses a bound (upper or lower) to prune sub‑trees that cannot contain a better solution. It is often applied to combinatorial optimization problems such as the knapsack and traveling‑salesman problems.

Code Examples

Hanoi Tower (Recursion, C++)

#include<cstdio>
int i; // step counter
void move(int n,char from,char to){
    printf("Step %d: move disk %d from %c to %c
", i++, n, from, to);
}
void Hanoi(int n,char start,char aux,char end){
    if(n==1){
        move(n,start,end);
    }else{
        Hanoi(n-1,start,end,aux);
        move(n,start,end);
        Hanoi(n-1,aux,start,end);
    }
}
int main(){
    int n;
    while(scanf("%d",&n)==1 && n){
        i=1;
        Hanoi(n,'1','2','3');
        printf("Total steps: %d
", i-1);
    }
    return 0;
}

Greedy Package (Java)

package cn.itcast.recursion;
import java.util.*;
public class GreedyPackage {
    private int MAX_WEIGHT = 150;
    private int[] weights = new int[]{35,30,60,50,40,10,25};
    private int[] values  = new int[]{10,40,30,50,35,40,30};
    private void packageGreedy(int capacity,int[] w,int[] v){
        int n = w.length;
        double[] r = new double[n];
        int[] idx = new int[n];
        for(int i=0;i<n;i++){
            r[i] = (double)v[i]/w[i];
            idx[i]=i;
        }
        // sort by value/weight descending
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(r[i] < r[j]){
                    double tmp=r[i]; r[i]=r[j]; r[j]=tmp;
                    int ti=idx[i]; idx[i]=idx[j]; idx[j]=ti;
                }
            }
        }
        int[] w1 = new int[n];
        int[] v1 = new int[n];
        for(int i=0;i<n;i++){
            w1[i]=w[idx[i]]; v1[i]=v[idx[i]];
        }
        int[] x = new int[n];
        int maxValue=0,totalWeight=0;
        for(int i=0;i<n;i++){
            if(w1[i] < capacity){
                x[i]=1;
                maxValue+=v1[i];
                totalWeight+=w1[i];
                capacity-=w1[i];
                System.out.println(w1[i]+"kg item added, value:"+v1[i]);
            }
        }
        System.out.println("Items taken:"+Arrays.toString(x));
        System.out.println("Total weight:"+totalWeight);
        System.out.println("Max value:"+maxValue);
    }
    public static void main(String[] args){
        GreedyPackage gp = new GreedyPackage();
        gp.packageGreedy(gp.MAX_WEIGHT,gp.weights,gp.values);
    }
}

Chessboard Tiling (Recursion, Java)

package cn.itcast.recursion;
public class ChessBoardProblem {
    private int[][] board;
    private int specialRow, specialCol, size, type=0;
    public ChessBoardProblem(int sr,int sc,int sz){
        specialRow=sr; specialCol=sc; size=sz; board=new int[sz][sz];
    }
    private void fill(int sr,int sc,int lr,int lc,int sz){
        if(sz==1) return;
        int sub=sz/2; type=type%4+1; int n=type;
        // top‑left
        if(sr<lr+sub && sc<lc+sub){
            fill(sr,sc,lr,lc,sub);
        }else{
            board[lr+sub-1][lc+sub-1]=n;
            fill(lr+sub-1,lc+sub-1,lr,lc,sub);
        }
        // top‑right
        if(sr<lr+sub && sc>=lc+sub){
            fill(sr,sc,lr,lc+sub,sub);
        }else{
            board[lr+sub-1][lc+sub]=n;
            fill(lr+sub-1,lc+sub,lr,lc+sub,sub);
        }
        // bottom‑left
        if(sr>=lr+sub && sc<lc+sub){
            fill(sr,sc,lr+sub,lc,sub);
        }else{
            board[lr+sub][lc+sub-1]=n;
            fill(lr+sub,lc+sub-1,lr+sub,lc,sub);
        }
        // bottom‑right
        if(sr>=lr+sub && sc>=lc+sub){
            fill(sr,sc,lr+sub,lc+sub,sub);
        }else{
            board[lr+sub][lc+sub]=n;
            fill(lr+sub,lc+sub,lr+sub,lc+sub,sub);
        }
    }
    public void print(int sr,int sc){
        fill(sr,sc,0,0,size);
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++) System.out.print(board[i][j]+" ");
            System.out.println();
        }
    }
    public static void main(String[] args){
        ChessBoardProblem cb = new ChessBoardProblem(0,1,4);
        cb.print(0,1);
    }
}

Coin Change (Dynamic Programming, Java)

public class Exchange {
    public int countWays(int[] penny,int n,int aim){
        if(n==0||penny==null||aim<0) return 0;
        int[][] dp = new int[n][aim+1];
        for(int i=0;i<n;i++) dp[i][0]=1;
        for(int i=1;penny[0]*i<=aim;i++) dp[0][penny[0]*i]=1;
        for(int i=1;i<n;i++){
            for(int j=0;j<=aim;j++){
                if(j>=penny[i]) dp[i][j]=dp[i-1][j]+dp[i][j-penny[i]];
                else dp[i][j]=dp[i-1][j];
            }
        }
        return dp[n-1][aim];
    }
}

Minimum Path Sum (Dynamic Programming, Java)

public class MinimumPath {
    public int getMin(int[][] map,int n,int m){
        int[][] dp = new int[n][m];
        for(int i=0;i<n;i++) dp[i][0]=dp[i-1][0]+map[i][0];
        for(int j=0;j<m;j++) dp[0][j]=dp[0][j-1]+map[0][j];
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+map[i][j];
            }
        }
        return dp[n-1][m-1];
    }
    private int min(int a,int b){return a<b?a:b;}
}

Backtracking Example – Permutations (Java)

List<List<Integer>> res = new LinkedList<>();
List<Integer> track = new LinkedList<>();
void permute(int[] nums){
    backtrack(nums,track);
}
void backtrack(int[] nums, List<Integer> track){
    if(track.size()==nums.length){
        res.add(new LinkedList<>(track));
        return;
    }
    for(int i=0;i<nums.length;i++){
        if(track.contains(nums[i])) continue;
        track.add(nums[i]);
        backtrack(nums,track);
        track.remove(track.size()-1);
    }
}

N‑Queens (Backtracking, C++)

vector<vector<string>> res;
vector<string> board;
vector<vector<string>> solveNQueens(int n){
    board.assign(n,string(n,'.'));
    backtrack(0);
    return res;
}
void backtrack(int row){
    if(row==board.size()){
        res.push_back(board);
        return;
    }
    int N=board[row].size();
    for(int col=0;col<N;col++){
        if(!isValid(row,col)) continue;
        board[row][col]='Q';
        backtrack(row+1);
        board[row][col]='.';
    }
}
bool isValid(int row,int col){
    int N=board.size();
    for(int i=0;i<N;i++) if(board[i][col]=='Q') return false;
    for(int i=row-1,j=col+1;i>=0 && j<N;i--,j++) if(board[i][j]=='Q') return false;
    for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--) if(board[i][j]=='Q') return false;
    return true;
}

Illustrative images: