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.

Wed Nov 8 17:36:19 PST 1995