Proof of correctness of this algorithm
It is a recursive definition, thus we can use induction. Let me first rephrase the algorithm a bit:

$$
CFP(n,A) = 
\begin{cases}
False&amp; \text{if }A=[\;]\\
True&amp; \text{if } first(A) + last(A) = n\\
CFP(n,tail(A))&amp;\text{if }first(A)+last(A)&lt;n \\
CFP(n,init(A))&amp;\text{otherwise}
\end{cases}
$$
where $tail(A)$ means all of $A$ but the first entry, $init(A)$ means all of $A$ but the last entry and $first(A)$ and $last(A)$ mean the first and last elements of $A$ respectively.

We now prove the statement by induction on the length of the array:


|A| = 0: $CFP (n,A)=False$ in accordance with the fact that there is no indices $i,j$ with $A_i+A_j=n$.
We assume the algorithm is correct for arrays of length $n$: Let $A$ be an array with $|A|=n+1$. If no pair of indices $i\leq j$ with $A_i+A_j=n$ exists, then either $CFP(n,A) = CFP(n,tail(A))$ or $CFP(n,A)=CFP(n,init(A)$. By induction hypothesis, the algorithm returns the correct result in both cases. On the other hand, if a pair $i\leq j$ of indices with the desired property exists, we distinguish the following cases:


$A_i=first(A)$: In this case, $first(A)+last(A)\geq n$ (because of how $A$ is ordered). Thus the algorithm either returns $True$ or $CFP(n,init(A))$. In the latter case $j$ is not the last index of $A$, thus the correctness of the result follows from the induction hypothesis.
$A_j = last(A)$: Analog to the previous case.
$first(A)&lt;A_i\leq A_j&lt;last(A)$: either $CFP(n,tail(A))$ or $CFP(n,init(A)$ is called. Since the a the statement is true for both $init(A)$ and $tail(A)$, the algorithm will correctly return $True$ by induction hypothesis.