CODEWITHSUNDEEP
javarecursion
User3
User3

Reputation: 2535

How to manually visualize the flow of the recursive algorithm?

I have an algorithm that generates partitions for a given number. I am asking for a way to write the flow of this program on paper so that I can understand it better.

I'm trying to trace the recursion within a loop in the method below:

 public static long calculate(final long totalSum, final long restriction) {
        appendLineToFile("Calculate function called with values: ");
        appendLineToFile("INPUT: totalSum: " + totalSum);
        appendLineToFile("INPUT: restriction: " + restriction);


        if (totalSum <= 1) {
            // recursive stopping condition
            appendLineToFile("==========recursive stopping condition==========");
            return 1;
        }
        long sum = 0;
        for (long k = 1; k <= restriction; k++) {
            appendLineToFile("Loop begins with k: " + k + " and restriction value: " + restriction);
            sum = sum + calculate(totalSum - k, k);
            appendLineToFile("For Ends" + " Sum in loop is: " + sum + " calculate(totalSum - k, k): " + (totalSum - k) + "," + k);

        }
       // appendLineToFile("=======Returning sum: " + sum + "===========");
        return sum;
    }

Here is the output for inputs 6 and 3: 

Calculate function called with values: 
INPUT: totalSum: 6
INPUT: restriction: 3
Loop begins with k: 1 and restriction value: 3
Calculate function called with values: 
INPUT: totalSum: 5
INPUT: restriction: 1
Loop begins with k: 1 and restriction value: 1
Calculate function called with values: 
INPUT: totalSum: 4
INPUT: restriction: 1
Loop begins with k: 1 and restriction value: 1
Calculate function called with values: 
INPUT: totalSum: 3
INPUT: restriction: 1
Loop begins with k: 1 and restriction value: 1
Calculate function called with values: 
INPUT: totalSum: 2
INPUT: restriction: 1
Loop begins with k: 1 and restriction value: 1
Calculate function called with values: 
INPUT: totalSum: 1
INPUT: restriction: 1
==========recursive stopping condition==========
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 1,1
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 2,1
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 3,1
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 4,1
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 5,1
Loop begins with k: 2 and restriction value: 3
Calculate function called with values: 
INPUT: totalSum: 4
INPUT: restriction: 2
Loop begins with k: 1 and restriction value: 2
Calculate function called with values: 
INPUT: totalSum: 3
INPUT: restriction: 1
Loop begins with k: 1 and restriction value: 1
Calculate function called with values: 
INPUT: totalSum: 2
INPUT: restriction: 1
Loop begins with k: 1 and restriction value: 1
Calculate function called with values: 
INPUT: totalSum: 1
INPUT: restriction: 1
==========recursive stopping condition==========
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 1,1
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 2,1
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 3,1
Loop begins with k: 2 and restriction value: 2
Calculate function called with values: 
INPUT: totalSum: 2
INPUT: restriction: 2
Loop begins with k: 1 and restriction value: 2
Calculate function called with values: 
INPUT: totalSum: 1
INPUT: restriction: 1
==========recursive stopping condition==========
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 1,1
Loop begins with k: 2 and restriction value: 2
Calculate function called with values: 
INPUT: totalSum: 0
INPUT: restriction: 2
==========recursive stopping condition==========
For Ends Sum in loop is: 2 calculate(totalSum - k, k): 0,2
For Ends Sum in loop is: 3 calculate(totalSum - k, k): 2,2
For Ends Sum in loop is: 4 calculate(totalSum - k, k): 4,2
Loop begins with k: 3 and restriction value: 3
Calculate function called with values: 
INPUT: totalSum: 3
INPUT: restriction: 3
Loop begins with k: 1 and restriction value: 3
Calculate function called with values: 
INPUT: totalSum: 2
INPUT: restriction: 1
Loop begins with k: 1 and restriction value: 1
Calculate function called with values: 
INPUT: totalSum: 1
INPUT: restriction: 1
==========recursive stopping condition==========
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 1,1
For Ends Sum in loop is: 1 calculate(totalSum - k, k): 2,1
Loop begins with k: 2 and restriction value: 3
Calculate function called with values: 
INPUT: totalSum: 1
INPUT: restriction: 2
==========recursive stopping condition==========
For Ends Sum in loop is: 2 calculate(totalSum - k, k): 1,2
Loop begins with k: 3 and restriction value: 3
Calculate function called with values: 
INPUT: totalSum: 0
INPUT: restriction: 3
==========recursive stopping condition==========
For Ends Sum in loop is: 3 calculate(totalSum - k, k): 0,3
For Ends Sum in loop is: 7 calculate(totalSum - k, k): 3,3
Result is: 7

Process finished with exit code 0

For the three initial loops I've written the following by hand:

enter image description here

Any help on how to traverse this by hand would be highly appreciated

Upvotes: 0

Views: 236

Answers (1)

default locale
default locale

Reputation: 13436

It's easier to understand an algorithm if you're walking through it step-by-step writing each action on a separate line.

You can use indentation to visualize the depth of recursive calls.

Here is how I would visualize this particular algorithm:

calculate(6,3)   //function call
sum = 0          //assignment
k = 1
    calculate(5,1)        //indentation shows the call hierarchy
    sum = 0
    k = 1
        calculate(4,1)
        sum = 0
        k = 1
            calculate(3,1)         
            sum = 0
            k = 1
                calculate(2,1)
                sum = 0
                k = 1
                    calculate(1,1)
                    return 1          
                sum = 1            //returning back to the caller
                return 1
            sum = 1
            return 1
        sum = 1
        return 1
    sum = 1
    return 1
sum = 1
k = 2
    calculate(4,2)
    ...

The output might get lengthy for larger inputs, but this approach makes it easier to look through recursive calls.

By the way, you don't actually need to write all of this by hand. It's relatively easy to add depth parameter to your method:

calculate(final long totalSum, final long restriction, int depth) {
     ....
     sum = sum + calculate(totalSum - k, k, depth+1);

Then you can create a method to output the line with proper indentation:

appendIndentedLine(depth, "calculate("+totalSum+....

I'll leave the implementation of appendIndentedLine for you as an exercise.

Upvotes: 1

Related Questions