How to implement C callback function in Swift?

Implement a Function WITHOUT Recursion in Java?

• Implement this function WITHOUT recursion: (in Java5) f(x,y) = { x-y, x<0 || y<0 { f(x-1,y) + f(x, y-1), otherwise the Recursive Solution is something like this, if it helps: public int f(int x, int y) { if(x<0 || y<0) { return x-y; } else {return f(x-1, y) + f(x, y-1); } } Serious Answers Only, please. This is a high level programming course.

• Answer:

  First, some mathematical preliminaries, in the case that m and n >= 0: (1) We can show that f(m, 0) = (m/2)(m + 3) by induction: first, note that f(0, 0) = f(-1, 0) + f(0, -1) = (-1 - 0) + (0 - -1) = 0 = (0/2)(0 + 3), so this formula holds for m = 0. If it is true that f(m, 0) = (m/2)(m + 3) for some m, then f(m + 1, 0) = f(m, 0) + f(m + 1, -1) = = (m/2)(m + 3) + (m + 1 - -1) = (m/2)(m + 3) + (m + 2) = (m² + 3m)/2 + (2m + 4)/2 = (m² + 5m + 4)/2 = (m + 1)(m + 4)/2 = [(m + 1)/2][(m + 1) + 3], so the formula holds for m + 1. By the principle of induction, for all integers m >= 0, f(m, 0) = (m/2)(m + 3). (2) Entirely analogously, we can show that f(0, n) = -(n/2)(n + 3). A natural question is, "How did I come up with these formulas?" The answer is that I used the recursive relation f(x, y) = f(x - 1, y) + f(x, y - 1) to successively reduce the size of the arguments of f until arriving at something with a negative in it. For example, in determining the first formula: f(m, 0) = f(m - 1, 0) + f(m, -1) = f(m - 1, 0) + (m - -1) = f(m - 1, 0) + (m + 1) = f(m - 2, 0) + f(m - 1, -1) + (m + 1) = f(m - 2, 0) + (m) + (m + 1) = f(m - 3, 0) + (m - 1) + (m) + (m + 1) ... = f(m - k, 0) + Σ[i: 1, k] (m + 2 - i) [there is a pattern emerging] ... = f(m - m, 0) + Σ[i: 1, m] (m + 2 - i) = Σ[i: 1, m] (m + 2) - Σ[i: 1, m] i = m(m + 2) - m(m + 1)/2 = (m/2)(m + 3) Since I just assumed the pattern continued, I then used an inductive proof to demonstrate that the formula I got by continuing the pattern was correct. One method of solution is to, in order to compute f(x, y) for x and y >= 0, define a matrix whose (m, n)th entry is f(m, n). You can do this by using the formulas above to initialize the first row and column of an (x + 1) by (y + 1) matrix, and then using the recursive relation to define the other cells. I'm not familiar enough with Java to provide the proper syntax, so I will provide C++ code -- the two should be similar enough to give you the idea. int f(int x, int y) { int fnVals[x+1][y+1]; // fnVals holds values for 0 <= m <= x (x + 1 values), and 0 <= n <= y (y + 1 values) if((x < 0) || (y < 0)) return x - y; else { int i, j; // loop variables for(i = 0; i <= x; i++) fnVals[i][0] = (i*(i+3))/2; for(j = 0; j <= y; j++) fnVals[0][j] = -(j*(j+3))/2; for(i = 1; i <= x; i++) { for(j = 1; j <= y; j++) { fnVals[i][j] = fnVals[i-1][j] + fnVals[i][j-1]; } } } return fnVals[x][y]; } There is some optimization you can perform on the code. For example, it is provable that f(m, n) = -f(n, m), which allows you to only compute values on the upper half of the matrix.