Chapter 7
Recursion

from
Introduction to Programming with Mathematica,
2nd Ed.

by
Richard J. Gaylord
Samuel N. Kamin
Paul R. Wellin

Copyright 1995 TELOS/Springer-Verlag

7.1 Fibonacci Numbers

Code from book

F[0] := 0

F[1] := 1

F[n_] := F[n-2] + F[n-1] /; n > 1

F[6]

Table[F[i], {i, 0, 8}]

TracePrint[F[4], F[_Integer] | F[_] + F[_]]

Exercises

Ex.1a

a[0] := 2
a[1] := 3
a[i_] := a[i-1] * a[i-2]

Ex.1b

b[0] := 0
b[1] := 1
b[i_] := b[i-2] - b[i-1]

Ex.1c

c[0] := 0
c[1] := 1
c[2] := 2
c[i_] := c[i-3] + c[i-2] + c[i-1]

Ex.2

FA[0] := 0
FA[1] := 0
FA[i_] := FA[i-2] + FA[i-1] + 1

Ex.3

c[0, n_] := n
c[i_, n_] := c[i-1, n]/2 /; EvenQ[c[i-1, n]]
c[i_, n_] := 3 c[i-1, n] + 1 /; OddQ[c[i-1, n]]

7.2 List Functions

Code from book

length[lis_] := length[Rest[lis]] + 1

length[{a, b, c}]

length[{}] := 0

length[{a, b, c}]

sumElts[lis_] := Apply[Plus, lis]

sumElts[lis_] := Fold[Plus, 0, lis]

sumElts[{}] := 0
sumElts[{x_, r___}] := x + sumElts[{r}]

addPairs[{}, {}] := {}
addPairs[{x1_, r1___}, {x2_, r2___}] :=
   Join[{x1 + x2}, addPairs[{r1}, {r2}]]

addPairs[{1, 2, 3}, {4, 5, 6}]

multPairwise[{}] := {}
multPairwise[{x_, y_, r___}] := Join[{x y}, multPairwise[{r}]]

multPairwise[{3, 9, 17, 2, 6, 60}]

deal[0] := {}

deal[n_] := Module[{dealt=deal[n-1]},
   Append[dealt,
         Complement[carddeck,dealt][[Random[Integer,{1,53-n}]]]]]

Exercises

Ex.1

removeLeadingSpaces[{}] := {}
removeLeadingSpaces[{" " | "\n", r___}] :=
   removeLeadingSpaces[{r}]
removeLeadingSpaces[L_] := L

Ex.2

sumOddElts[{}] := 0
sumOddElts[{x_, y___}] := x + sumOddElts[{y}] /;
   IntegerQ[x] && OddQ[x]
sumOddElts[{x_, y___}] := sumOddElts[{y}]

Ex.3

sumEveryOtherElt[{}] := 0
sumEveryOtherElt[{x_}] := x
sumEveryOtherElt[{x_, y_, r___}] := 
   x + sumEveryOtherElt[{r}]

Ex.4

addTriples[{}, {}, {}] := {}
addTriples[{x1_, y1___}, {x2_, y2___}, {x3_, y3___}] :=
    Join[{x1+x2+x3}, addTriples[{y1}, {y2}, {y3}]]

Ex.5

multAllPairs[{}] := {}
multAllPairs[{_}] := {}
multAllPairs[{x_, y_, r___}] :=
       Join[{x y}, multAllPairs[{y, r}]]

Ex.6

maxPairs[{}, {}] := {}
maxPairs[{x_, r___}, {y_, s___}] :=
       Join[{Max[x, y]}, maxPairs[{r}, {s}]]

Ex.7

interleave[{}, {}] := {}
interleave[{x_, r___}, {y_, s___}] :=
       Join[{x, y}, interleave[{r}, {s}]]

7.3 Thinking Recursively

Code from book

doubleUptoZero[{}] := {}
doubleUptoZero[{0, y___}] := {0, y}
doubleUptoZero[{x_, y___}] := Join[{2x}, doubleUptoZero[{y}]]

doubleUptoZero[{2, 3, 0, 4, 5}]

doubleUptoZero[{2, 3, 4, 5}]

runEncode[{}] := {}
runEncode[{x_}] := {{x, 1}}
runEncode[{x_, r___}] := 
   Module[{R = runEncode[{r}]},              (* R = {{y, k},...} *)
      Module[{p = First[R], rst = Rest[R]},  (* p = {y, k}       *)
            If[x == First[p],                (* First[p] = y     *)
               Join[{{x, p[[2]]+1}}, rst],   (* p[[2]] = k       *)
               Join[{{x, 1}}, R]]]]

runEncode[{x_, r__}] :=
   runEncode[{r}] /. {{y_, k_}, s___} ->
                     If[x==y,
		       {{x, k+1}, s},
		       {{x, 1}, {y, k}, s}]

runEncode[{9, 9, 9, 9, 9, 4, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5}]

runEncode[L_] := Map[({#, 1})&, L] //.
   {x___, {y_, i_}, {y_, j_}, z___} -> {x, {y, i+j}, z}

maxima[{}] := {}
maxima[{x_, r___}] := Join[{x}, Select[maxima[{r}], (#>x)&]]

maxima[{9, 2, 10, 3, 14, 9}]

maxima[Rest[{9, 2, 10, 3, 14, 9}]]

Select[%, (#>9)&]

Join[{9}, %]

interleave2[{x_, r___}, {y_, s___}] :=
   Join[{x, y}, interleave2[{r}, {s}]]

interleave2[{}, M_] := M
interleave2[L_, {}] := L

interleave2[{a, b, c}, {1, 2, 3, 4, 5}]

interleave2[{a, b, c, d, e, f}, {1, 2, 3}]

Exercises

Ex.1

prefixMatch[L_, {}] := {}
prefixMatch[{}, M_] := {}
prefixMatch[{x_, r___}, {x_, s___}] :=
   Join[{x}, prefixMatch[{r}, {s}]]
prefixMatch[{x_, r___}, {y_, s___}] := {}

Ex.2

runEncode2[{}] := {}
runEncode2[{x_}] := {x}
runEncode2[{x_, r__}] :=
    runEncode2[{r}] /. {{{y_, k_}, s___} ->
                       If[x==y, {{x, k+1}, s}, {x, {y, k}, s}],
                       {y_, s___} ->
                       If[x==y, {{x, 2}, s}, {x, y, s}]}

Ex.3

runEncode[{}] := {}
runEncode[{x_, r___}] := runEncode[x, 1, {r}]

runEncode[x_, k_, {}] := {{x, k}}
runEncode[x_, k_, {x_, r___}] := runEncode[x, k+1, {r}]
runEncode[x_, k_, {y_, r___}] :=
   Join[{{x, k}}, runEncode[y, 1, {r}]]

Ex.4

maxima[{}] := {}
maxima[{x_, r___}] := maxima[x, {r}]

maxima[x_, {}] := {x}
maxima[x_, {y_, r___}] := maxima[x, {r}] /; x >= y
maxima[x_, {y_, r___}] := Join[{x}, maxima[y, {r}]]

Ex.5

interleave2[{}, M_] := M
interleave2[L_, {}] := L
interleave2[{x_, r___}, {y_, s___}] :=
   Join[{x, y}, interleave2[{r}, {s}]]

interleave3[{}, M_, N_] := interleave2[M, N]
interleave3[L_, {}, N_] := interleave2[L, N]
interleave3[L_, M_, {}] := interleave2[L, M]
interleave3[{x1_, r1___}, {x2_, r2___}, {x3_, r3___}] :=
        Join[{x1, x2, x3}, interleave3[{r1}, {r2}, {r3}]]

Ex.6

runDecode[{}] := {}
runDecode[{{x_, k_}, r___}] := 
   Join[Table[x, {k}], runDecode[{r}]]

Ex.7

kSublists[0, L_] := {{}}
kSublists[k_, {}] := {}
kSublists[k_, L_] :=
   Module[{ksubs = kSublists[k-1, Rest[L]]},
      Join[Map[(Join[{First[L]}, #])&, ksubs],
          kSublists[k, Rest[L]]]]

7.4 Recursion and Symbolic Computations

Code from book

ddx[c_] := 0
ddx[x^n_] := n x^(n-1)
ddx[u_ + v_] := ddx[u] + ddx[v]

ddx[x^2 + x^3]

ddx[5 x^3]

ddx[c_] =.     (* remove the rule ddx[c_] := 0 *)

ddx[c_?NumberQ] := 0

ddx[5 x^3]

Clear[ddx]
ddx[c_?NumberQ] := 0
ddx[x] := 1
ddx[u_ + v_] := ddx[u] + ddx[v]
ddx[u_ - v_] := ddx[u] - ddx[v]
ddx[u_ v_] := u ddx[v] + v ddx[u]
ddx[u_ / v_] := (v ddx[u] - u ddx[v]) / v^2
ddx[u_^c_?NumberQ] := c u^(c-1) ddx[u]

ddx[5 x^3]

Trace[ddx[x^3], ddx]

ddx[(x + 2x^2)^4]

ddx[u_ - v_] := ddx[u + -1 v]
ddx[u_ / v_] := ddx[u (v^-1)]

ddx[x^2/(x-1)]

?ddx

ddx[u_ - v_] =.
ddx[u_ / v_] =.

Simplify[ddx[x/(x-1)]]

FullForm[Hold[ddx[x/(x-1)]]]

Exercises

Ex.1

ddx[c_?NumberQ] := 0
ddx[x] := 1
ddx[u_ + v_] := ddx[u] + ddx[v]
ddx[u_ - v_] := ddx[u] - ddx[v]
ddx[u_ v_] := u ddx[v] + v ddx[u]
ddx[u_ / v_] := (v ddx[u] - u ddx[v]) / v^2
ddx[u_ ^ c_?NumberQ] := c u^(c-1) ddx[u]

ddx[sin[u_]] := cos[u] * ddx[u]
ddx[cos[u_]] := -sin[u] * ddx[u]
ddx[tan[u_]] := ddx[sin[u]/cos[u]]

Ex.2

ddx[c_?NumberQ] := 0
ddx[x] := 1
ddx[u_ + v_] := ddx[u] + ddx[v]
ddx[u_ - v_] := ddx[u] - ddx[v]
ddx[u_ v_] := u ddx[v] + v ddx[u]
ddx[u_ / v_] := (v ddx[u] - u ddx[v]) / v^2
ddx[u_ ^ c_?NumberQ] := c u^(c-1) ddx[u]

ddx[u_] := 0 /; nox[u]

nox[c_?NumberQ] := True
nox[x] := False
nox[y_] := True /; Head[y] == Symbol && y =!= x
nox[u_ + v_] := nox[u] && nox[v]
nox[u_ - v_] := nox[u] && nox[v]
nox[u_ v_] := u nox[v] && v nox[u]
nox[u_ / v_] := nox[u] && nox[v]
nox[u_ ^ c_?NumberQ] := nox[u]

Ex.3

ddx[c_?NumberQ, y_] := 0
ddx[x_, x_] := 1
ddx[y_, x_] := 0 /; FreeQ[y, x]
ddx[u_ + v_, x_] := ddx[u, x] + ddx[v, x]
ddx[u_ - v_, x_] := ddx[u, x] - ddx[v, x]
ddx[u_ v_, x_] := u ddx[v, x] + v ddx[u, x]
ddx[u_ / v_, x_] := (v ddx[u, x] - u ddx[v, x]) / v^2
ddx[u_ ^ c_?NumberQ, x_] := c u^(c-1) ddx[u, x]

7.5 Gaussian Elimination

Code from book

m = {{1, 2}, {4, 5}}

b = {3, 6}

LinearSolve[m, b]

m = N[Table[1/(i+j-1), {i,15}, {j,15}]];
b = Table[Random[], {15}];

xs = LinearSolve[m, b]

m . xs - b

solve[S_] :=
   Module[{E1 = First[S], x2toxn = solve[elimx1[S]]},
      Module[{b1 = Last[E1], a11 = First[E1], 
              a12toa1n = Drop[Rest[E1], -1]},
         Join[{(b1 - a12toa1n . x2toxn) / a11}, x2toxn]]]

solve[{{a11_, b1_}}] := {b1/a11}

elimx1[S_] := Map[subtractE1[S[[1]], #]&, Rest[S]]
subtractE1[E1_, Ei_] :=
   Module[{z = Ei[[1]]/E1[[1]]},
      Module[{newE1 = z * Rest[E1]},
         Rest[Ei] - newE1]]

solve[A_, B_] := solve[Transpose[Join[Transpose[A], {B}]]]

solve[{{1, 2}, {4, 5}}, {3,6}]

Exercises

Ex.1

solve[S_] :=
   Module[{PS = pivot[S]},
      Module[{E1 = First[PS],
              x2toxn = solve[elimx1[PS]]},
            Module[{b1 = Last[E1],
                    a11 = First[E1],
                    a12toa1n = Drop[Rest[E1], -1]},
               Join[{(b1 - a12toa1n . x2toxn) / a11}, x2toxn]]]]

solve[{{a11_, b1_}}] := {b1/a11}

elimx1[S_] := Map[subtractE1[S[[1]], #]&, Rest[S]]

subtractE1[E1_, Ei_] := 
    Module[{z = Ei[[1]]/E1[[1]]},
                Module[{newE1 = z * Rest[E1]},
                                Rest[Ei] - newE1]]

pivot[Q_] :=
     Module[{p, ST1, pivotrow},
        ST1 = Transpose[Q][[1]];  (* first elements of rows of Q *)
        p = Position[ST1, x_/; x!= 0];
        If[p == {},
           Print["Matrix is singular"]; Q,
           pivotrow = p[[1]][[1]];
           Join[{Q[[pivotrow]]}, Delete[Q, pivotrow]]
        ]]

Ex.2

Ex.3

solveUpper[{{ann_}}, {bn_}] := {bn/ann}
solveUpper[{A1_, rA__}, {b1_, rB__}] :=
   Module[{subsoln = solveUpper[Map[Rest, {rA}], {rB}]},
      Join[{(b1 - Dot[Rest[A1], subsoln]) / First[A1]}, subsoln]]

rotateMatrix[A_] := Reverse[Map[Reverse, A]]

solveLower[A_, B_] :=
    Reverse[solveUpper[rotateMatrix[A], Reverse[B]]]

Ex.4

LUdecomp1[S_] :=
   Module[{mults = multipliers[S[[1,1]], Rest[S]]},
     Module[{Sprime = elimx1[mults, Map[Rest, S]]},
       Module[{LU = LUdecomp1[Sprime]},
         {expandL[mults, LU[[1]]], expandU[First[S], LU[[2]]]}]]]

LUdecomp1[{{a11_}}] := { {{1}}, {{a11}} }

expandU[S1_, U_] := Join[{S1}, Map[Join[{0},#]&, U]]

expandL[mults_, L_] :=
      Transpose[expandU[Join[{1}, mults], Transpose[L]]]

elimx1[mults_, subS_] :=
      Table[subS[[i+1]]-mults[[i]]*subS[[1]], {i, 1, Length[mults]}]

multipliers[S11_, restS_] := Map[(#/S11)&, Transpose[restS][[1]]]

LUdecomp2[S_] :=
   Module[{soln = LUdecomp1[S]},
      soln[[1]] - IdentityMatrix[Length[S]] + soln[[2]]]

7.6 Trees

Code from book

fruittree = {"fig", {"date", {"kumquat"}, {"papaya"}}, {"mango"}}

minInTree[{lab_}] := lab
minInTree[{lab_, lc_, rc_}] :=
   Sort[{lab, minInTree[lc], minInTree[rc]}][[1]]

height[{lab_}] := 0
height[{lab_, lc_, rc_}] := 1 + Max[height[lc], height[rc]]

minInTree[fruittree]

printTree[t_] := printTree[t, 0]

printTree[{lab_}, k_] := printIndented[lab, 3k]
printTree[{lab_, lc_, rc_}, k_] :=
   (printIndented[lab, 3k];
    Map[(printTree[#, k+1])&, {lc, rc}];)
printIndented[x_, spaces_] :=
   Print[Apply[StringJoin, Table["  ", {spaces}]], x]

printTree[fruittree]

Htree = {" ABEHONST", {" AT", {" "}, {"AT", {"T"}, {"A"}}},
           {"BEHONS", {"EON", {"E"}, {"ON", {"O"}, {"N"}}},
           {"BHS", {"BH", {"H"}, {"B"}}, {"S"}}}}

encodeString[str_] :=
   Flatten[Map[encodeChar, Characters[str]]]

encodeChar[c_, {_, lc_, rc_}] :=
   If[stringMemberQ[First[lc], c],     (* if c in left subtree *)
      Join[{0}, encodeChar[c, lc]],    (* prepend 0 *)
      Join[{1}, encodeChar[c, rc]]]    (* otherwise prepend 1 *)

encodeChar[_, {_}] := {}

encodeChar[c_] := encodeChar[c, Htree]

encodeString["HONEST ABE"]

decode[code_, {ch_}] :=      (* leaf node - label is character *)
   StringJoin[ch, decode[code, Htree]]
decode[{0, r___}, {_, lc_, _}] := decode[{r}, lc]
decode[{1, r___}, {_, _, rc_}] := decode[{r}, rc]
decode[{}, _] := ""

decode[code_] := decode[code, Htree]

Exercises

Ex.1

sumNodes[{lab_}] := lab
sumNodes[{lab_, lc_, rc_}] := 
   lab + sumNodes[lc] + sumNodes[rc]

Ex.2

catNodes[{lab_}] := lab
catNodes[{lab_, lc_, rc_}] := 
   StringJoin[lab, catNodes[lc], catNodes[rc]]

Ex.3

balanced[t_] := balancedHeight[t][[2]]
balancedHeight[{lab_}] := {0, True}
balancedHeight[{lab_, lc_, rc_}] :=
   Module[{lbh, rbh},
      lbh = balancedHeight[lc];
      If[lbh[[2]], rbh = balancedHeight[rc];
                   If[rbh[[2]] && Abs[lbh[[1]]-rbh[[1]]] <= 1,
                      {Max[lbh[[1]], rbh[[1]]] + 1, True},
                      {0, False}],  (* height doesn't matter *)
                   {0, False}]]  (* height doesn't matter *)

Ex.4

listLevel[0, t_] := {t[[1]]}
listLevel[n_, {lab_}] := {}
listLevel[n_, {lab_, lc_, rc_}] := Join[listLevel[n-1, lc],
                                        listLevel[n-1, rc]]

Ex.5

minInTree[{lab_}] := lab
minInTree[{lab_, subtrees__}] :=
     Sort[Join[{lab}, Map[minInTree, {subtrees}]]][[1]]

height[{lab_}] := 0
height[{lab_, subtrees__}] := 1 + Apply[Max, Map[height, {subtrees}]]

printTree[t_] := printTree[t, 0]

printTree[{lab_}, k_] := printIndented[lab, 3k]
printTree[{lab_, subtrees__}, k_] :=
    (printIndented[lab, 3k]; Map[(printTree[#, k+1])&, {subtrees}];)

printIndented[x_, spaces_] :=
    Print[Apply[StringJoin, Table[" ", {spaces}]], x]

Ex.6

HTreeSort[trees_] := Sort[trees, (#1[[1, 2]] < #2[[1, 2]])&]

joinHTrees[{{{cl_, wt_}, kids___}}] := {cl, kids}
joinHTrees[{{{cl1_, wt1_}, kids1___},
            {{cl2_, wt2_}, kids2___},
            trees___}] :=
  joinHTrees[
     HTreeSort[{{{StringJoin[cl1, cl2], wt1+wt2},
                  {cl1, kids1}, {cl2, kids2}}, trees}] ]

constructHTree[t_] := joinHTrees[HTreeSort[t]]

htnode[a_,b_] := {{{a,b}}}
testlist = Join[htnode[" ",6],htnode["A",3],
        htnode["B",1],htnode["E",5],htnode["H",2],htnode["N",2],
         htnode["O",2],htnode["S",3],htnode["T",3]]

Ex.7

Htree = {" ABEHONST", {" AT", {" "}, {"AT", {"T"}, {"A"}}},
          {"BEHONS", {"EON", {"E"}, {"ON", {"O"}, {"N"}}},
               {"BHS", {"BH", {"H"}, {"B"}}, {"S"}}}};

makeTreeTable[prefix_, {ch_}] := {ch->prefix}
makeTreeTable[prefix_, {_, left_, right_}] :=
  Join[makeTreeTable[Join[prefix, {0}], left],
       makeTreeTable[Join[prefix, {1}], right]]

makeTreeTable[tree_] := makeTreeTable[{}, tree]

HtreeRules = makeTreeTable[Htree]

encodeString[str_, rules_] :=
      Flatten[Characters[str] /. rules]

encodeString[str_] := encodeString[str, HtreeRules]

7.7 Dynamic Programming

Code from book

FF[0] := 0
FF[1] := 1
FF[n_] := FF[n] = FF[n-2] + FF[n-1]

TracePrint[FF[4], FF[_Integer] | (FF[_] = FF[_] + FF[_])]

?FF

Exercises

Ex.1

F[0] := 0
F[1] := 1
F[n_ /; EvenQ[n]] := 2 F[n/2-1] F[n/2] + F[n/2]^2
F[n_ /; OddQ[n]] := F[(n-1)/2+1]^2 + F[(n-1)/2]^2

Ex.2

FF[0] := 0
FF[1] := 1
FF[n_ /; EvenQ[n]] := FF[n] = 2 FF[n/2-1] FF[n/2] + FF[n/2]^2
FF[n_ /; OddQ[n]] := FF[n] = FF[(n-1)/2+1]^2 + FF[(n-1)/2]^2

Fcount[0] := 0
Fcount[1] := 0
Fcount[n_ /; EvenQ[n]] := Fcount[n/2-1] + Fcount[n/2] + Fcount[n/2]^2 + 1
Fcount[n_ /; OddQ[n]] := Fcount[(n-1)/2+1] + Fcount[(n-1)/2] + 1

Ex.3

cc[0, n_] := n
cc[i_, n_] := (cc[i, n] = cc[i-1, n]/2) /; EvenQ[c[i-1, n]]
cc[i_, n_] := (cc[i, n] = 3 cc[i-1, n] + 1) /; OddQ[c[i-1, n]]

7.8 Higher-Order Functions and Recursion

Code from book

map[f_, {}] := {}
map[f_, {x_, y___}] := Join[{f[x]}, map[f, {y}]]

map[Cos, {1, 2, 3}]

nest[f_, x_, 0] := x
nest[f_, x_, n_] := f[nest[f, x, n-1]]

nest[Sin, theta, 4]

repeat[f_, L_, pred_] := L /; pred[Drop[L, -1], Last[L]]
repeat[f_, L_, pred_] := repeat[f, Append[L, f[Last[L]]], pred]

repeatCount[f_, n_] := repeat[f, {n}, MemberQ]

plus4mod20[x_] := Mod[x+4, 20]

repeatCount[plus4mod20, 0]

Exercises

Ex.1

fold[f_, x_, {}] := x
fold[f_, x_, {a_, r___}] := fold[f, f[x, a], {r}]

foldList[f_, x_, {}] := {x}
foldList[f_, x_, {a_, r___}] := 
   Join[{x}, foldList[f, f[x, a], {r}]]

nestList[f_, x_, 0] := {x}
nestList[f_, x_, n_] := Join[{x}, nestList[f, f[x], n-1]]

Ex.2

repeat[f_, L_, pred_] := L /; pred[Drop[L, -1], Last[L]]
repeat[f_, L_, pred_] := repeat[f, Append[L, f[Last[L]]], pred]

tryC[n_] := repeat[cc[n,#]&, {n}, (#2==1)&]

Ex.3

landMineWalk[] :=
   repeat[(#+{{0,1},{0,-1},{1,0},{-1,0}}[[Random[Integer,
                                                {1, 4}]]])&,
         {{0,0}},
         MemberQ[#1, #2]&]

Ex.4

map2[f_, g_, {}, {}] := {}
map2[f_, g_, L_, {}] := g[L, {}]
map2[f_, g_, {}, M_] := g[{}, M]
map2[f_, g_, {a_, r___}, {b_, s___}] := 
        Join[{f[a, b]}, map2[f, g, {r}, {s}]]

7.9 Debugging

Code from book

Trace[F[2]]

Trace[F[2], F]

TracePrint[F[2], F[_]]

TracePrint[F[2], F[n_Integer] -> n]

F[n_] := (Print[n]; F[n-2] + F[n-1]) /; n > 1

F[4]

f[x_, y_] := (Print["Rule 1: ", x, y]; e)

f[n] := Table[i, {i, -n, n}]

f[10]

f[{x_, r___}, y_] := If[x<0, {y, f[{r}]}, f[{r}]]

f[{}, _] := {}

f[{-5, 4, 17}, -1]

g[{x_, r___}, y_] := If[x<0, {y, g[r, y]}, g[r, y]]

g[{}, _] := {}

g[{-5, 4, 17, 12, 21}, -1]

h[x_] := h[x-1] + h[x+1]

h[0] := 0

h[1]