15
1
Cops' thread
In this thread, your task is to make a recursion-based program/function to generate any integer series. Robbers will try and find a shorter non-recursive solution over in the Robbers' thread.
Challenge synopsis
In many languages, recursive functions can significantly simplify a programming task. However, the syntax overhead for a proper recursion may limits its usability in code-golf.
The cops will create a program or function taking a single integer n
, which will generate the first n
entries of an integer series, using only recursion1. They should also make sure there is a shorter nonrecursive way to generate the sequence in order to mark their entry as safe.
The robbers will try to find a shorter program or function in the same language, generating the same integer series, using no recursion2.
If the cops' submission is not cracked within ten days (240 hours), the cop will prove it was in fact possible to have a shorter non-recursive approach by revealing their own solution. They may then mark their submission as safe.
The winner of the cops challenge will be the shortest (according to code-golf) recursion-based submission marked safe.
The winner of the robbers challenge will be the robber who cracked the most solutions.
1: It only needs to be recursive in syntax; you don't need to worry about for example tail call optimization.
2: Again, non-recursive in syntax; so you can't post a recursive solution and claim its compiled to a loop thanks to tail call optimization.
Submission requirements
Each submission will take a single integer n
(zero- or one-based). The submission will then output or return the first n
entries of an integer series of choice. (note that this integer series must not depend on n
). The input and output method may differ between the recursive and non-recursive approach. The integer series may be any deterministic series with a length of at least 5. The series should be explained properly.
Your submission does not have to work for arbitrary large n
, but should work for at least n=5
. The non-recursive approach must be able to work up to at least the same n
as the recursive approach, or up to n=2^15-1
, whichever is smaller.
Recursion
For the sake of this challenge, recursion is defined as creating the desired sequence using a function (or function-like construct) that calls itself (or calls a sequence of functions that ends up calling itself; this includes constructs like the Y combinator). The recursion depth should go to infinity as n
goes to infinity. The non-recursive approach is anything that is not recursive.
For Thyme where
for
is done by recursive behind, isfor
recursive or loop? – l4m2 – 2018-03-07T03:27:31.390Can I say a code works for arbitrarily large
n
if it's theoretically correct, but it cannot be run due to time or memory constraints? – Bubbler – 2018-03-07T06:39:37.440@Bubbler Certainly, but at least
n=5
must be computed – Sanchises – 2018-03-07T06:50:27.297@l4m2 Not all languages can compete. It seems like this language does not have a native way of not using recursion (unless
xfor
is available through some kind of import?) so perhaps this language cannot compete. – Sanchises – 2018-03-07T07:27:44.937A recursive that don't go that much when n go large, is it a recursive? – l4m2 – 2018-03-07T14:21:34.903
@l4m2 You mean like a recursion depth of
O(log n)
or? Please be more specific. – Sanchises – 2018-03-07T14:46:32.910maybe O(log n) or O(1)[f(x)=x%3?f(x-1)*x:x], or anything – l4m2 – 2018-03-07T14:59:01.250
@l4m2 The latter makes zero sense.But the former is completely fine. I quote, The recursion depth should go to infinity as n goes to infinity. Anything over
O(1)
fulfills that requirement. – Sanchises – 2018-03-07T15:38:31.340why zero sense? – l4m2 – 2018-03-07T15:55:22.117
@l4m2 It doesn' seem to generate an integer series of length
n
but only then
th entry. Correct me if I'm wrong. – Sanchises – 2018-03-08T06:59:19.560@Sanchises If it's not recursive i can use it in the loop solution – l4m2 – 2018-03-08T12:01:22.710
Can we choose a sequence in which a program to compute it must use recursion (Assuming such a sequence exists)? – caird coinheringaahing – 2018-03-08T16:31:05.453
@caird No. You must provide your own nonrecursive solution to mark your entry as safe. Also, I do not think such a sequence exists as any computable sequence can be generated with a Turing-complete language, which does not need to support recursion – Sanchises – 2018-03-08T17:22:38.550
@cairdcoinheringaahing Fractran doesn't have recursion, and it's still TC. Anything that is computable with recursion can also be able to compute without recursion. – user202729 – 2018-03-11T09:03:01.610
Is it correct that the series technically needs to be infinite? – flawr – 2018-03-12T21:59:14.383
@flawr It may be a finite series, but the program should be agnostic of that (to fulfill the requirement that recursion depth should go to infinite as
n
goes to infinity). Your program may exhibit undefined behaviour ifn
is larger than the sequence length. The sequence length must be larger than 5. – Sanchises – 2018-03-13T11:02:38.133@flawr (I am not necessarily a fan of this definition, but as you can see by the number of comments, there's been some debate over what exactly constitutes recursion. This definition so far seems to hold up to the spirit of the challenge. If you have another suggestion on how to handle finite sequences, feel free to comment!) – Sanchises – 2018-03-13T11:05:29.560
Aww, the titles could've been something like (for the cops and robbers respectively): Visit the Robber's Thread and Visit the Cop's Thread – caird coinheringaahing – 2018-04-01T12:55:24.947