In attempt to understand recursion better, I tried to print some output within my code so that I could study the steps.
#include <tuple> #include <string> #include <iostream> #include <map> #include "print.h" std::tuple<int, int, int> find_max_crossing_subarray(int A[], int low, int mid, int high) { int max_left, max_right; int left_sum = std::numeric_limits<int>::min(); int sum = 0; for(int i = mid; i >= low; i--) { sum += A[i]; if(sum > left_sum) { left_sum = sum; max_left = i; } } int right_sum = std::numeric_limits<int>::min(); sum = 0; for(int j = mid + 1; j <= high; j++) { sum += A[j]; if(sum > right_sum) { right_sum = sum; max_right = j; } } return std::make_tuple(max_left, max_right, left_sum + right_sum); } std::tuple<int, int, int> find_max_subarray(int A[], int low, int high) { if(high == low) { return std::make_tuple(low, high, A[low]); } else { int mid = (high + low) / 2; std::tuple<int, int, int> left(find_max_subarray(A, low, mid)); std::cout << "left: "; print(left); int left_low, left_high, left_sum; std::tie(left_low, left_high, left_sum) = left; std::tuple<int, int, int> right(find_max_subarray(A, mid + 1, high)); std::cout << "right: "; print(right); int right_low, right_high, right_sum; std::tie(right_low, right_high, right_sum) = right; std::tuple<int, int, int> cross(find_max_crossing_subarray(A, low, mid, high)); std::cout << "cross: "; print(cross); int cross_low, cross_high, cross_sum; std::tie(cross_low, cross_high, cross_sum) = cross; if(left_sum >= right_sum && left_sum >= cross_sum) { return left; } else if(right_sum >= left_sum && right_sum >= cross_sum) { return right; } else { return cross; } } } int main() { int arr_3[3] = {-3, 2, 3}; int arr_4[4] = {5, -23, 1, 44}; int arr_6[6] = {5, -23, 1, 44, -2, 5}; int arr[16] = {-23, 3, 9 ,7, -12, 87, -25, 2, 3, 5, 32, -8, 6, -82, 3, 9}; print(arr_4, 4); std::tuple<int, int, int> maple(find_max_subarray(arr_4, 0, 3)); print(maple); return 0; } OUTPUT::
5 -23 1 44 left: 0 0 5 right: 1 1 -23 cross: 0 1 -18 left: 0 0 5 left: 2 2 1 right: 3 3 44 cross: 2 3 45 right: 2 3 45 cross: 0 3 27 2 3 45 I understand the first three lines of the output (that is, where the left, right, cross begin). But I do not understand where the fourth line and beyond come from. I tried tracing back the functions and I keep thinking I should get left: 1 1 -23 in my fourth line of output after cross: 0 1 -18.
EDIT:
I should point out that after left: 2 2 1, although it's hard to visualize, I understand somewhat. The recursion has reached the end and the code is just cascading backwards.
SECOND EDIT:
I guess what is happening in the fourth line is that the very first find_max_subarray is completing and it is returning the first if statement in the function code. Now it is moving to the second find_max_subarray.
THIRD EDIT:
I guess my confusion is that the code doesn't cascade backwards but instead just returns to the very first call after it reaches the end of the recursion.
FOURTH EDIT:
When I go out to six elements though it seems like it doesn't simply return to the first call.
5 -23 1 44 -2 5 left: 0 0 5 right: 1 1 -23 cross: 0 1 -18 left: 0 0 5 right: 2 2 1 cross: 0 2 -17 left: 0 0 5 left: 3 3 44 right: 4 4 -2 cross: 3 4 42 left: 3 3 44 right: 5 5 5 cross: 3 5 47 right: 3 5 47 cross: 2 5 48 2 5 48 I mean I guess it's because the sub array has three elements as opposed to two. So there are two pairs as opposed to one. It makes sense when you take it for granted but can't see it visually.
LAST EDIT:
So when I go out to 8, it goes in pairs. First two elements and then return the original call. The next two pairs and return the call. I'm not exactly sure why though in the odd case it won't return the call until both the first and second and first and third pairs have completed.
5 -23 1 44 -2 5 6 -3 left: 0 0 5 right: 1 1 -23 cross: 0 1 -18 left: 0 0 5 left: 2 2 1 right: 3 3 44 cross: 2 3 45 right: 2 3 45 cross: 0 3 27 left: 2 3 45 left: 4 4 -2 right: 5 5 5 cross: 4 5 3 left: 5 5 5 left: 6 6 6 right: 7 7 -3 cross: 6 7 3 right: 6 6 6 cross: 5 6 11 right: 5 6 11 cross: 2 6 54 2 6 54 PROBLEM SOLVED:
The problem I was having in understanding the recursion is that for each recursive step I was using the original high value. I actually wrote it down on paper in blocks using the correct high and everything came together.
