Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-01-31 Recursion

posted Jan 31, 2019, 6:05 AM by Konstantinovich Samuel   [ updated Feb 27, 2019, 5:55 AM ]
Goal: Recursion day 3. 

Tail Recursion:
    -No Pending Operations
    -Generally a partially computed answer is stored as a parametes
*pending operations:  An operation that is waiting for another operation to complete.
    e.g. 1 + foo(n-1)  //the 1 + has to wait for the foo, so it would be pending the completion of the recursive call.

Write the following  algorithm together with your neighbors:

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

You must write it 3 different ways:
-tail recursive

Tail recursion is optimized in some languages.
-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.


How can we write the function:
public static ArrayList<Integer> makeAllSums(int n)
-Returns an array list of all subset totals of the numbers 1 to n inclusive.

makeAllSums(3) returns an ArrayList [0, 3, 2, 5, 1, 4, 3, 6]
(the order isn't important right now)

The reason is you can sum to 0,1,2,3,4,5 and 6 in the following ways:

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

This helps 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 3
               yes /  \ no 
                  /    \
          include 2     include 2
         yes /  \ no      yes /  \ no 
            /    \           /    \
                    3           3                 5            0

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

Git Repos:
-Now you should go back and make your MKS21X repo's private (it is free to do so!)
-Do not make the new repos private until the term is over (and you don't need to dispute something)
-Some of you do not commit enough. It is not acceptable to only commit your final working version.
I reserve the right to deny credit for any lab/project that does not show your progress from empty methods up to a working version (including tests)

Let us start simple:

HW Create a git repo:
Should include the following class + methods

public class recursion{
    /*You may write additional private methods */

    /*Recursively find the sqrt using Newton's approximation
     *tolerance is the allowed percent error the squared answer is away from n.
     *precondition: n is non-negative

    public static double sqrt(double n, double tolerance){


    /*Recursively find the n'th fibbonaci number in linear time
     *fib(0) = 0
     *fib(1) = 1
     *fib(5) = 5
     *precondition: n is non-negative
    public static int fib(int n){


    /*As Per classwork*/
    public static ArrayList<Integer> makeAllSums(int n){