Coding a recursive function for highest possible input

Challenge

You are given the following function:- which is the same as:-

with the base cases q(r, b, L) = 1 whenever r ≤ L, q(r, 0, L) = 0, if r > L and q(r, 0, L) = 1, if r ≤ L.

Your task is to code a program that takes r as input, and outputs the value of q(r, r - L, L) for all L taking integer values from 1 to (r-1), where r is any nonnegative integer.

Example 1

Input

Enter the value of r: 2

Output

q(2,1,1) = 0.3333333333

Example 2

Input

Enter the value of r: 3

Output

q(3,2,1) = 0.1

q(3,1,2) = 0.5

Winning criterion

The code that can correctly output q(r, r-L, L) for all L taking integer values from 1 to (r-1), for the highest value of r, in less than 300 seconds. In case of a tie, the code with lesser runtime will be considered. As this is a runtime-based challenge, I shall test all submissions on my machine.

• Your sum/product notations both use the letter k as their variable. I think this is technically valid, but it might be easier to read if you used two different letters. Commented Dec 7, 2014 at 19:03
• Which of the two base cases takes priority when r < L and b = 0? And what value of b will be used in the winning criterion? Commented Dec 7, 2014 at 23:21
• @PeterTaylor let me guess: are you working on a closed-form? Commented Dec 8, 2014 at 7:42
• q(r, r-1, 1) == 2(r!)^2/(2r)! (oeis.org/A001700) and r(r, 1, r-1) == (r-1)/(r+1) (trivial). Haven't checked the others yet. Commented Dec 8, 2014 at 17:23
• In the interests of clarity, q(r,r-1,1) is the reciprocal of A001700. Commented Dec 10, 2014 at 10:12

Java

I've applied some algebraic transformation and dynamic programming.

public class CodeGolf42234 {
public static void main(String[] args) {
int r = Integer.parseInt(args[0]);
for (int L = 1; L < r; L++) System.out.println(qDouble5(r, r-L, L));
}

private static double qDouble5(int _r, int _b, int L) {
double[][] q = new double[_r+1][_b+1];
for (int r = 0; r <= L; r++) {
for (int b = 0; b < q[r].length; b++) q[r][b] = 1;
}
for (int r = L + 1; r < q.length; r++) {
for (int b = 1 + (r - L - 1)/L; b < q[r].length; b++) {
double sum = 0, m = 1;
for (int k = 0; k <= L; k++) {
sum += m * q[r-k][b-1];
m = m * (r - k) / (r + b - 1 - k);
}
q[r][b] = sum * b / (r + b);
}
}
return q[_r][_b];
}
}

• Thank you for the submission. On my system (Windows, Netbeans IDE), the highest value of r that can be evaluated using this code, in under 300 seconds (297 seconds) is 731. Good job, Peter! :) Commented Dec 10, 2014 at 10:36

Java

Here's a recursive solution. Just like you wanted. You can always uncomment the output and display it if you want.

import java.util.ArrayList;
import java.util.Scanner;

{
static ArrayList<Double> answers = new ArrayList<Double>();
public static void main(String[]args)
{
Scanner scanner = new Scanner(System.in);
int r = scanner.nextInt();
for(int b=r-1; b!=0; b--)
for(int L=r-1; L!=0; L--)

//  int i=-1;
//      for(int b=r-1; b!=0; b--)
//          for(int L=r-1; L!=0; L--)
//              System.out.println("q("+r+", "+b+", "+L+") = "+answers.get(++i));

}

public static double formulate(double r, double b, double L)
{
if(b==0)
if(r>L)
return 0.0;
else
return 1;
if(r<=L)
return 1;
double partone = (b/(r+b));
double result = 0.0;
for(int k=1; k<=L; k++)
{
result+=summation(r, b, k) * (b/(r+b-k)) * formulate(r-k, b-1, L);
}
return (partone * formulate(r, b-1, L)) + result;
}

public static double summation(double r, double b, int k)
{
double rb = r+b;
double mul=r/rb;
for(int i=1; i<k; i++)
{
mul*=(r-i)/(rb-i);
}
return mul;
}
}