P oblem Gene aliza ion o Designing
Recu si e Algo i hms
Diana Bo ego(B), I ene Ba ba, Miguel To o, and Ca melo Del Valle
Depa amen o de Lenguajes y Sis emas In o m´
a icos, Uni e sidad de Se illa, Se illa, Spain
{dianabn,i eneb ,miguel o o,ca melo}@us.es
Abs ac . This pape ocuses on he di icul y o uni e si y s uden s o acqui e,
wi hin compu a ional hinking, he skills o sol e ce ain p oblems h ough ecu -
sion. The acquisi ion o his ype o easoning is essen ial o unde s and he di -
e en p oblem sol ing echniques ha a e based on ecu si e algo i hms, such as
di ide and conque o dynamic p og amming. The e o e, i s , he gene aliza ion
o p oblems is p oposed as a s a egy o designing ecu si e algo i hms. As a
second s ep, ha gene aliza ion is o malized h ough a speci ica ion shee ha
con ains di e en ields ha co espond o he cha ac e is ics ha a e ele an o
sol e a p oblem ecu si ely.
Keywo ds: Recu si e algo i hms ·Compu a ional hinking ·P oblem
gene aliza ion
1 In oduc ion
Compu e science uni e si y s uden s ha e he need o de elop compu a ional hinking,
which is he men al p ocess used o o mula e p oblems whose solu ions can be ca -
ied ou by a compu e . Compu a ional hinking includes skills such as modeling and
b eaking down p oblems, p ocessing da a, c ea ing algo i hms and gene alizing hem.
The e a e se e al de ini ions ela ed o compu a ional hinking in he li e a u e.
Re iewing publica ions abou his opic, Wing e al. [6], who made he e m com-
pu a ional hinking amous, p esen he ollowing de ini ion: “Compu a ional hinking
in ol es sol ing p oblems, designing sys ems, and human beha io unde s anding, by
d awing on he concep s undamen al o compu e science. Compu a ional hinking
includes a ange o men al ools ha e lec he b ead h o he ield o compu e science.”
The e o e, s uden s mus acqui e compu a ional hinking o be able o ca y ou p ob-
lem sol ing h ough modula iza ion, op-down analysis, bo om-up analysis, ecu sion,
and so on. Pa icula ly, he unde s anding and applica ion o his las concep o ecu -
sion [3,4] equi es he s uden s o make an ex a men al e o . They usually unde s and
and lea n mo e easily he i e a i e o mula ions o p oblems. Howe e , o unde s and he
ecu si e o mula ion, a special ype o hinking is needed, and he e o e o be able o
use ecu si e hinking [7]. This p esen s a di icul y ha makes a men al p edisposi ion
necessa y ha is no always equen o easy o each depending on each pe son.
In de ail, he ecu si e esolu ion o a p oblem is aised when he speci ica ion o
i s solu ion is made based on he solu ion o o he p oblems o he same na u e bu a
c
smalle size. The e o e, e e y ecu si e de ini ion has (i) base case(s), encompassing
and esol ing cases whe e he esolu ion o he p oblem is di ec and does no equi e
he use o he unc ion being de ined; (ii) ecu si e case(s), which a e hose whose
esolu ion does equi e he use o he unc ion being de ined; and (iii) size o he p ob-
lem, which is a ca dinal indica ing he dimension o he p oblem o be sol ed, and ha
dec eases in each subp oblem. Thus, a ecu si e algo i hm is one ha exp esses he
solu ion o a p oblem in e ms o in oking i sel .
As an example, he de ini ion and ecu si e algo i hm o he esolu ion o he ac-
o ial o a numbe na e shown below.
n!=1n=0
n∗(n−1)!n>0
N (In ege n){
Ns;
i {n == 0}{
s=1;
}else {
s=n* (n-1);
}
e u n s;
}
Algo i hm 1: Recu si e algo i hm o
calcula ing he Fac o ial numbe (in Ja a)
No all ecu si e de ini ions a e sui able o building an algo i hm. To be adequa e,
i mus ha e: (1) a leas one base case; (2) in each ecu si e s ep he size should be
educed (which implies ha he execu ion o he algo i hm will end).
Taking all his in o accoun , and o acili a e he acquisi ion and applica ion o ecu -
si e hinking, his pape p oposes o ca y ou wo s eps p io o he design o a ecu si e
algo i hm o sol e a gi en p oblem, as shown in Fig. 1. Speci ically, hese s eps a e:
1. Gene aliza ion o he p oblem h ough a se o p oblems [1]. Mo e p ecisely, gene -
alizing consis s o adding p ope ies o he o iginal p oblem o conside i a pa icula
case o a wide se o p oblems.
Fig. 1. P oposed app oach o designing ecu si e algo i hms
2. Speci ica ion o he solu ion o he p oblem h ough a p ede ined speci ica ion shee
based on he p e ious gene aliza ion made. This shee con ains di e en ields ha
co espond o he cha ac e is ics ha a e ele an o sol e his p oblem ecu si ely.
No e ha he goal o he p oposed app oach is no o p o ide a o mal me hod bu o
acili a e he acquisi ion o skills ela ed o he design o ecu si e algo i hms. Fo his,
we use ou expe ience in he design o ypes in he con ex o objec -o ien ed p og am-
ming o concep ualize he popula ion o p oblems ha a e gene a ed when designing
ecu si e algo i hms, i.e., when he gene aliza ion is ca ied ou . In such con ex , he
co ec de ini ion o he size o he p oblems ( ha is a de i ed p ope y o such p ob-
lems) is key when analyzing he co ec ness o he gene aliza ion pe o med. To be
mo e p ecise, when gene alizing a p oblem o designing a ecu si e algo i hm, i is
necessa y o e i y ha he e is an ini ial p oblem, and ha all he p oblems a e o de ed
by size.
The emainde o he pape is s uc u ed as ollows: Sec . 2p esen s he gene aliza-
ion o p oblems h ough se s o p oblems, Sec . 3includes he speci ica ion shee o
he p oblem solu ion by ecu sion along wi h some illus a i e examples, and Sec . 4
p esen s a c i ical discussion o he p oposed app oach. Finally conclusions a e d awn
and u u e wo k is p oposed in Sec . 5.
2 P oblem Gene aliza ion
This sec ion p esen s he p oposed app oach: Sec . 2.1 explains he concep o se o
p oblems in he con ex o p oblem gene aliza ion, Sec . 2.2 de ails how such se o
p oblems can be used o p oblem gene aliza ion, and, las ly, Sec . 2.3 includes he gen-
e al schema o ecu sion ha is ela ed o he p oposed p oblem gene aliza ion.
2.1 Se o P oblems
In a ecu si e de ini ion i is always necessa y o s a om a se o p oblems P=
{p,p0,p1,...}. In such se each p oblem is cha ac e ized by a se o p ope ies x=
{x0,x1,...}. Each p ope y o a se o p oblems can be ca ego ized as:
– Sha ed: sha ed p ope ies a e de ined as p ope ies o he se o p oblems ha ake
he same alue o all p oblems o such se .
– Indi idual: indi idual p ope ies a e de ined as p ope ies o he se o p oblems ha
ake di e en alues o each p oblem o such se .
Bo h sha ed and indi idual p ope ies can be ca ego ized as basic o de i ed p op-
e ies. The inclusion o he la e , unlike he o me , is op ional since hei alues can
be calcula ed om he alues o he basic p ope ies. De i ed p ope ies a e ypically
included o he sake o cla i y. I is impo an o cla i y ha he basic indi idual p op-
e ies a e he ones ha unequi ocally iden i y each p oblem wi hin he se o p oblems,
i.e., he e a e no wo p oblems wi h he same alues o all basic indi idual p ope ies.
Mo eo e , each p oblem o a se o p oblems has a speci ic size, ha is a de i ed
indi idual p ope y. To be mo e p ecise, he size o a p oblem is de ined as an in ege
g ea e han o equal o ze o ha is ela ed o he complexi y o he p oblem (i.e., how
a is he p oblem om a case base). The e a e di e en ways o de ining he size o a
p oblem. Howe e , i is necessa y o check he co ec ness o such de ini ion by consid-
e ing ha he size o a p oblem should (1) be a unc ion o e some o he p ope ies o
he p oblem, (2) be educed as a base case is app oached.
The p oblems o a se o p oblems can be ca ego ized as:
– Base case o a se o p oblems P: a p oblem o a se o p oblems is a base case when
i has a di ec solu ion (i.e., wi hou pe o ming a ecu si e call). A p oblem ha is
a base case has a small size. Mo eo e , he e can exis se e al base cases wi hin he
same se o p oblems.
– Recu si e case o a se o p oblems P: a p oblem o a se o p oblems is a ecu si e
case when i does no ha e a di ec solu ion (i.e., i is necessa y o pe o m a ecu si e
call o sol e i ). The solu ion o a ecu si e p oblem is de ined by combining he
solu ions ela ed o p oblems o smalle sizes (i.e., subp oblems).
– All p oblems, in he se o p oblems o in e es , e i y a p edica e d(x). This p edi-
ca e es ablishes he domain o alid p oblems.
2.2 P oblem Gene aliza ion
The key idea o sol e a p oblem in a ecu si e way is based on exp essing i s solu ion in
e ms o ope a ions o e solu ions o a se o p oblems o smalle size. Fo his, in many
cases i becomes necessa y o imagine ha se o p oblems om he o iginal p oblem
(i.e., p oblem gene aliza ion).
To be mo e p ecise, he p oblem gene aliza ion consis s o he ollowing s eps:
1. Adding, i necessa y, a se o addi ional p ope ies o hose ha al eady had he
p oblem and classi y hem in o basic, de i ed, indi idual, sha ed, e c.
2. De ining he domain o p oblems o in e es h ough a p edica e.
3. De ining he size o a p oblem.
4. S a ing he base cases and he ecu si e cases.
5. Speci ying how each ecu si e case is educed o subp oblems wi h a smalle size.
6. Speci ying how each ecu si e case’s solu ion is ela ed o ha o i s subp oblems.
7. Speci ying he solu ion o base case.
8. Indica ing which o he p oblems in he p oblem se co esponds o he o iginal
p oblem.
2.3 Gene al S uc u e o a Recu si e Algo i hm
In o de o design a ecu si e algo i hm o sol ing a p oblem wi h pa ame e s x(o
ype X) i is ypically ad ised o pe o m 2 unc ions. The i s one (i.e., unc ion ,
c . Algo i hm 2) ecei es as inpu pa ame e s o he ini ial p oblem o sol e x, and pe -
o ms an ini ial call o a second unc ion g(c . Algo i hm 3). The la e is a ecu si e
unc ion ha ecei e as inpu pa ame e bo h he pa ame e s o p oblem o sol e xand
he addi ional p ope ies ha a e conside ed a e p oblem gene aliza ion (i.e., yo ype
Y). F om now on he p ope ies o he gene alized p oblem will be bo h he pa ame e s
o he o iginal p oblem and he new p ope ies added. Func ion is op ional. The e a e
cases whe e he unc ion gis su icien and does no appea . This si ua ion is ound
when i is possible o conside a b oad se o p oblems by a ying wi hin a domain he
alues o he pa ame e s. One unc ion calls he o he as depic ed in Algo i hm 2.
S (X x) {
e u n g(x,y_0);
}
S g(X x, Y y){
...
}
Algo i hm 2: Func ions in a ecu si e
algo i hm (in Ja a)
The gene al s uc u e o a ecu si e algo i hm is shown in Algo i hm 3.
S (X x) {
e u n g(x,y_0);
}
S g(X x, Y y){
Ss;
i (b(x,y){
s = sb(x,y);
} else {
Y y_0 = sp_0(x,y);
S s_0 = g(x,y_0);
Y y_1 = sp_1(x,y);
S s_1 = g(x,y_1);
...;
Y y_{m-1} = sp_{m-1}(x,y);
S s_{m-1} = g(x,y_{m-1});
s = c(s_0,s_1,...,s_{m-1},x,y);
}
e u n s;
}
Algo i hm 3: Gene al s uc u e o a
ecu si e algo i hm (in Ja a)
As ollows, concep s ela ed o Algo i hm 3a e de ailed:
–x: pa ame e s o p oblem o ype X.
–S: ype o he solu ion.
–y: addi ional p ope ies (o ype Y) o he se o p oblems ha a e included a e
p oblem gene aliza ion.
–size(x,y): unc ion ha e u ns he size o he p oblem (x,y).
–d(x,y): p edica e es ablishing he domain o (x,y).
–b(x,y): p edica e ha shows i a p oblem is a base case

–sb(x,y): unc ion ha e u ns he solu ion o a base case.
–np(x,y): unc ion ha e u ns he numbe o subp oblems ela ed o (x,y).
–m=np(x,y): he numbe o subp oblems
–y0,y1,...,ym−1: a iables o ype Y ha s o e he subp oblems ela ed o (x,y).To
be mo e p ecise, yi e e s o he i- h p oblem ela ed o (x,y).
–sp0(x,y),sp1(x,y),...,spm−1(x,y): unc ions ha e u n he subp oblems ela ed o
(x,y). To be mo e p ecise, spi(x,y) e u ns he he i- h p oblem ela ed o (x,y).
–s0,s1,...,sm−1: a iables o ype Ss o ing he solu ions o he subp oblems ela ed
o (x,y). Thus, si e e s o he solu ion o he i- h p oblem ela ed o (x,y).
–c(s0,s1,...,x,y): unc ion ha e u ns he solu ion o xby combining he solu ions
o i s subp oblems.
3 Speci ica ion Shee o he P oblem Gene aliza ion
This sec ion de ails he shee ha is p oposed o speci ying he p oblem gene aliza ion
p e iously explained (c . Sec . 2.2). The pa s ha a e included in such speci ica ion
shee a e explained as ollows:
– Types: in o ma ion ela ed o he ypes ha a e ele an o sol e he p oblem, e.g.,
he ype o he solu ion.
– Sha ed p ope ies: sha ed p ope ies o he se o p oblems ha is ob ained a e he
p oblem gene aliza ion.
– Indi idual p ope ies: indi idual p ope ies o he se o p oblems ha is ob ained
a e he p oblem gene aliza ion.
– Size: size o he p oblem, which is a unc ion o e he p ope ies o such p oblem.
– Ini ial ins an ia ion: ini ial alue ha is gi en o he indi idual p ope ies.
– Base cases: i gi es in o ma ion abou whe he a p oblem is a base case. In case he e
is mo e han one condi ion ha causes a p oblem o be conside ed a base case, one
pe line is speci ied.
– Solu ion o base cases: solu ions o he p oblems ha a e base cases. I he e is
mo e han one base case condi ion, he solu ion is p o ided o each o hem on
di e en lines, using he ope a o →.
– Numbe o subp oblems: numbe o subp oblems ha need o be sol ed o ob ain
he solu ion o he o iginal p oblem.
– Subp oblems: subp oblems ha need o be sol ed o ob ain he solu ion o he o ig-
inal p oblem. When de e mining hem, i is only necessa y o speci y he changes
ha occu in he indi idual p ope ies wi h espec o he o iginal p oblem, since he
sha ed p ope ies emain he same o all p oblems. Di e en subp oblems a e also
speci ied in di e en lines, wi h he ope a o →. In case ha only one subp oblem
needs o be sol ed, i s is de e mined h ough he condi ion o selec which one, wi h
he o ma ci→si. On he o he hand, when he e a e mo e han one subp oblem, a
supe sc ip is added o dis inguish he e e ed one ( 0
→,1
→,...).
– Combine: unc ion ha ob ains he solu ion o he o iginal p oblem by combining
he solu ions ha a e ob ained o he subp oblems.
As can be obse ed, he e a e many simila i ies be ween he elemen s o he spec-
i ica ion shee and he elemen s o he gene al s uc u e o a ecu si e algo i hm ( o
de ails c . Table 1).
Table 1. Rela ion be ween he speci ica ion shee and he ecu si e algo i hm.
Speci ica ion shee Gene al s uc u e o a ecu si e algo i hm
Types S,X,Y
Sha ed p ope ies
Indi idual p ope ies
Domain d(x,y)p edica e
Size size(x,y) unc ion
Ini ial ins an ia ion y0
Base cases b(x)p edica e
Solu ion o base cases sb(x,y) unc ion
Numbe o subp oblems np(x,y) unc ion
Subp oblems sp0,sp1,.... unc ions
Combine c(s0,s1,...,x,y) unc ion
3.1 Running Examples
This sec ion includes how he p oposed app oach is applied o wo illus a i e examples.
Fo each example, (1) he speci ica ion shee ela ed o he p oblem gene aliza ion and
(2) he ela ed ecu si e algo i hm a e de ailed.
Example 1. Calcula ing he Fibonacci numbe s [5].The Fibonacci numbe is ecu -
si ely de ined as ollows:
(n)=nn≤1
(n−1)+ (n−2)o he wise
Rega ding such de ini ion, a ecu si e algo i hm can be designed (c . Algo i hm 4)
acco ding o he p oblem gene aliza ion ha is speci ied in Table 2.
N ib(In ege n){
Ns;
i (n<=1){
=n;
} else {
In ege y_0 = n-1;
s_0 = ib(y_0);
In ege y_1 = n-2;
s_1 = ib(y_1);
s = s_0+s_1;
}
e u n s;
}
Algo i hm 4: ib - Recu si e algo i hm
o calcula ing Fibonacci numbe s (in
Ja a)
Table 2. Speci ica ion shee o sol ing he Fibonacci p oblem.
Fibonacci
Types Solu ion: In ege
Sha ed p ope ies
Indi idual p ope ies n: In ege
Domain n≥0
Size n
Ini ial ins an ia ion
Base cases n≤1
Solu ion o base cases n
Numbe o subp oblems 2
Subp oblems (n)0
→(n−1)
(n)1
→(n−2)
Combine s0+s1
Example 2. Bina y sea ch in a so ed lis [2].The bina y sea ch algo i hm is an e i-
cien sea ch me hod, which inds he posi ion o a a ge alue wi hin a so ed lis . To
do his, he algo i hm di ides he lis by i s middle elemen in o wo smalle sublis s,
and compa es he a ge alue wi h he middle elemen . I hey a e equal, he sea ch
ends. I he a ge alue is lowe , i mus be (i p esen ) in he i s hal o he lis , in he
second hal o he wise. The p ocess con inues un il he a ge is ound, o un il i eaches
an emp y sublis due o he a ge alue is no in he lis ( e u ning −1), which a e wo
base cases condi ions.
Fo his p oblem, he ollowing sha ed p ope ies a e conside ed: (1) lis o elemen s
ls, (2) elemen ha is sea ched m, and (3) size o he lis o elemen s, ha is a de i ed
p ope y n. To gene alize, he ollowing indi idual p ope ies a e es ablished: (1) index
i ha indica es he s a ing posi ion o he sublis conside ed o he cu en subp oblem,
(2) index j ha indica es he ending posi ion o he sublis conside ed o he cu en
subp oblem, and (3) he middle posi ion k, a de i ed p ope y, be ween i,j. As de ailed,
he p oblem only in okes one o he wo possible subp oblems.
Mo e de ails a e gi en in Table 3, and he ela ed algo i hms a e depic ed (c .
Algo i hm 5). As can be obse ed, he main algo i hm (c . bs in Algo i hm 5) pe o ms
he ini ial call o he ecu si e algo i hm (c . bs gin Algo i hm 5) acco ding o he ini ial
ins an ia ion o he indi idual p ope ies.
4 Discussion
The p oposal p esen ed in his pape p esen s se e al ad an ages. To be mo e p ecise,
on he one hand, he ac o analysing he solu ion o a p oblem be o e ca ying ou
he implemen a ion i sel acili a es e o isola ion as well as e o de ec ion. On he
o he hand, he gene aliza ion o p oblems and he ela ed speci ica ion shee allow o
es ablishing a sys ema ic way o designing a ecu si e algo i hm o sol ing a speci ic
p oblem.
Based on ou expe ience as eache s o p og amming subjec s in he i s uni e si y-
le el cou ses, s uden s a e eluc an a i s o speci y he gene aliza ion o p oblems
h ough he speci ica ion shee . On he one hand, his is some hing new o hem, and
he e o e, a pe iod o lea ning and aining is equi ed. In his pe iod, s uden s acqui e
he necessa y knowledge ega ding he meaning and use ulness o each o he p ope ies
ha a e included in he speci ica ion shee . On he o he hand, speci ying he p oblem
gene aliza ion is mo e ime-consuming han di ec ly implemen ing he solu ion. Mo e-
o e , he applica ion o he p oposed app oach makes sense o p oblems ha p esen s
ce ain cha ac e is ics. To be mo e p ecise, he p oposed app oach makes mo e sense
in he case ha designing an e icien ecu si e algo i hm o sol ing a p oblem is no
i ial o he s uden s, i.e., p e ious analysis is equi ed (e.g., c . Example 2). Howe e ,
he e a e some p oblems, i.e., hose p oblems whose de ini ion i sel is ecu si e, ha
Table 3. Speci ica ion shee o sol ing he Bina y sea ch p oblem.
Bina y sea ch
Types Solu ion: In ege
Sha ed p ope ies ls: Lis <E>
e: E
n: In ege (de i ed - size o ls)
Indi idual p ope ies i: In ege
j: In ege
k: In ege (de i ed), k=(j+i)/2
Domain i∈[0,n)&& j∈[i,n]
Size j−i
Ini ial ins an ia ion (0,n)
Base cases e=ls[k]
j−i<1
Solu ion o base cases e== ls[k]→k
j−i<1→−1
Numbe o subp oblems 1
Subp oblems e>ls[k]→(k,j)
e≤ls[k]→(i,k)
Combine s0