Courses‎ > ‎AP Computer Science 2‎ > ‎konstantinovich‎ > ‎

2018-02-05

posted Feb 5, 2018, 10:15 AM by Konstantinovich Samuel   [ updated Feb 6, 2018, 7:36 PM ]
Goal: Recursion day 3. 

Tail Recursion
    • No pending operations.  A pending operation happens after the recursive call completes,   e.g. 1 + foo(n-1)  //the 1 + has to wait for the foo, so it would be pending.
    • Partially computed answer is stored as a parameter 
    • Java does not have tail recursion optimization: tail recursion still blows the stack after less than 11,000 calls, much less if you have more parameters. 

Write the following 3 algorithms together with your neighbors:

int sumDigits(int n)      
e.g.
sumDigits(1234) evaluates to 10, because 1+2+3+4 

Write it 3 different ways:
-loop
-recursive
-tail recursive




How can we write the function:
public static boolean canMakeSum(int n, int target)
-Return true when you can add up a subset of the numbers 1 to n inclusive to add up to the target value.
e.g.
canMakeSum(3,x)

This can sum to 0,1,2,3,4,5 and 6 in the following ways:

Include 
number?         
True/False
1   2   3            Sum
T   T   T            6      (include all 3)
T   T   F            3
T   F   T            4
T   F   F            1  (include 1, but not 2 or 3)
F   T   T            5
F   T   F            2
F   F   T            3
F   F   F            0

canMakeSum(3,5) -> True
canMakeSum(3,0) -> True
canMakeSum(3,15) -> False

This function is not a particularly useful one because all integers from 1 to the sum of all the values can be achieved, and recursive backtracking is not needed to find them. However it does help you practice using recursion to test all of a set of possibilities and then backtrack and try others. 

You can use this to just test out the testing of all possible combinations, by printing your sum when you reach the base case. This means that in your tree of possibilities:

                include 1
               yes /  \ no 
                  /    \
          include 2     include 2
         yes /  \ no      yes /  \ no 
            /    \           /    \
                    3           1                 2            0

Printing out your base case would print the leaves of the tree!






Comments