This is our third and final example of recursion. In this example, the user inputs an array and a sum-bound, and the program will report all sums which are less than or equal to the sum-bound, and which can be formed from the given array elements. For example, if the array is
5 6 22 28
and the sum-bound is 30, then the following sums qualify: 5, 6, 22, 28, 5+6, 5+22, 6+22.
Here is the program:
3
4 /* another example of recursion; the function FindAllSums below
5 will find all possible sums <= a given value from a given
6 array */
7
8
9 #define MaxArrayLength 100
10
11
12 int TestArray[MaxArrayLength], /* array to test FindAllSums() */
13 NTest, /* actual length of that array */
14 L; /* the value of ``K'' in our test of the function */
15
16
17 struct SNode {
18 /* Participate[I] is 1 or 0, depending on whether the I-th array
19 element participates in a sum or not */
20 int Participate[MaxArrayLength];
21 struct SNode *Link; /* link to next node */
22 };
23
24
25 typedef struct SNode *SPtrType;
26
27
28 GetTestArrayAndL()
29
30 { int I = 0,TA;
31
32 printf("enter an array of integers, terminated by 0\n");
33 while (1) {
34 scanf("%d",&TA);
35 if (TA == 0) break;
36 TestArray[I++] = TA;
37 }
38 NTest = I;
39 printf("enter L\n");
40 scanf("%d",&L);
41 }
42
43
44 /* the function Display will print to the screen the contents of a linked
45 list, using the first NArrayElts from each Participate field */
46
47 Display(ListPtr,NArrayElts)
48 SPtrType ListPtr; int NArrayElts;
49
50 { SPtrType TmpPtr = ListPtr; int I;
51
52 while (TmpPtr) {
53 printf("participants: ");
54 for (I = 0; I < NArrayElts; I++)
55 if (TmpPtr->Participate[I]) printf("%d ",I);
56 printf("\n");
57 TmpPtr = TmpPtr->Link;
58 }
59 }
60
61
62 /* finds the tail of the list headed by ListPtr */
63
64 SPtrType FindTail(ListPtr)
65 SPtrType ListPtr;
66
67 { SPtrType TmpPtr = ListPtr;
68
69 while (TmpPtr->Link) TmpPtr = TmpPtr->Link;
70 return TmpPtr;
71 }
72
73
74 /* the function SingletonSum will see if the single element X[I]
75 forms a "sum" <= K; if so, the function will create a struct
76 for that sum, and return a pointer to it; otherwise the
77 function will return 0 */
78
79 SPtrType SingletonSum(X,I,K)
80 int X[],I,K;
81
82 { SPtrType TmpPtr;
83
84 if (X[I] <= K) {
85 TmpPtr = (SPtrType) calloc(1,sizeof(struct SNode));
86 TmpPtr->Participate[I] = 1;
87 TmpPtr->Link = 0;
88 return TmpPtr;
89 }
90 else return 0;
91 }
92
93
94 /* the function FindAllSums will return a pointer to a list of all
95 possible sums <= K, formed from the first N elements of X */
96
97 SPtrType FindAllSums(X,N,K)
98 int X[],N,K;
99
100 { SPtrType Ptr_a,Ptr_b,Ptr_c,Tail_a,Tail_b,TmpPtr;
101
102 /* check the nonrecursive case first */
103 if (N == 1) return SingletonSum(X,0,K);
104
105 /* in order to set up a recursion, think of all sums <= K as
106 falling into one of three categories:
107
108 (a) those sums which use only the elements X[0],...,X[N-2],
109 (b) those sums which make use of our "newest" element, X[N-1]
110 in combination with the sums in (a), and
111 (c) the sum consisting of X[N-1] by itself
112
113 we can find the sums in these three categories as follows:
114
115 for category (a), use the call FindAllSums(X,N-1,K)
116 for category (b), use the call FindAllSums(X,N-1,K-X[N-1]),
117 and set Participate[N-1] in each sum found
118 for category (c), use the call Singleton(X,N-1,K)
119
120 we will find all three lists, and then combine them into one big
121 list, whose head is our return value */
122
123 /* get list (a) */
124 Ptr_a = FindAllSums(X,N-1,K);
125
126 /* get list (b) */
127 Ptr_b = FindAllSums(X,N-1,K-X[N-1]);
128 if (Ptr_b) {
129 TmpPtr = Ptr_b;
130 do {
131 TmpPtr->Participate[N-1] = 1;
132 TmpPtr = TmpPtr->Link;
133 } while (TmpPtr);
134 }
135
136 /* get list (c) */
137 Ptr_c = SingletonSum(X,N-1,K);
138
139 /* OK, now put the three lists together into one big list whose head
140 will be the return value */
141
142 /* now put the three lists together and return */
143 if (Ptr_a) {
144 Tail_a = FindTail(Ptr_a);
145 if (Ptr_b) Tail_a->Link = Ptr_b;
146 else Tail_a->Link = Ptr_c;
147 }
148 if (Ptr_b) {
149 Tail_b = FindTail(Ptr_b);
150 Tail_b->Link = Ptr_c;
151 }
152 if (Ptr_a) return Ptr_a;
153 else if (Ptr_b) return Ptr_b;
154 else return Ptr_c;
155 }
156
157
158 main()
159
160 { SPtrType SumsPtr;
161
162 GetTestArrayAndL();
163 SumsPtr = FindAllSums(TestArray,NTest,L);
164 Display(SumsPtr,NTest);
165 }
166
167
168 heather% a.out
169 enter an array of integers, terminated by 0
170 5 6 0
171 enter L
172 7
173 participants: 0
174 participants: 1
175 heather% !!
176 a.out
177 enter an array of integers, terminated by 0
178 5 6 22 28 0
179 enter L
180 30
181 participants: 0
182 participants: 0 1
183 participants: 1
184 participants: 0 2
185 participants: 1 2
186 participants: 2
187 participants: 3
Lines 168ff: Here are the sample runs. The output format is rather austere. To explain how to read it, consider Line 184: In saying that the ``participants'' are 0 and 2, it means that TestArray[0] and TestArray[2] participate in the sum, i.e. 5+22.
Lines 17-22: Here is the major data type. The comments in Lines 18-19 reflect our remark above concerning the format of the output.
Lines 97ff: Here is the recursive function which finds all the sums. Note that it does this by returning a pointer to a list of sums. (This function looks long, but it is mainly comments.)
In Line 103, we check the nonrecursive case, i.e. the case which can't be split up into further calls. Remember, this is also the mechanism by which infinite recursion is avoided.
The basic idea of the recursion is explained in the comments in Lines 105-121.