View source for Stair-climbing puzzle

{{task}}
From [http://lambda-the-ultimate.org/node/1872 Chung-Chieh Shan] (LtU):

Your stair-climbing robot has a very simple low-level API: the "step" function takes no argument and attempts to climb one step as a side effect. Unfortunately, sometimes the attempt fails and the robot clumsily falls one step instead. The "step" function detects what happens and returns a boolean flag: true on success, false on failure. 

Write a function "step_up" that climbs one step up [from the initial position] (by repeating "step" attempts if necessary). Assume that the robot is not already at the top of the stairs, and neither does it ever reach the bottom of the stairs. How small can you make "step_up"? Can you avoid using variables (even immutable ones) and numbers?

Here's a pseudo-code of a simple recursive solution without using variables:
<pre>
func step_up()
{
    if not step() {
        step_up();
        step_up();
    }
}
</pre>
Inductive proof that step_up() steps up one step, if it terminates:
* Base case (if the step() call returns true): it stepped up one step. QED
* Inductive case (if the step() call returns false): Assume that recursive calls to step_up() step up one step. It stepped down one step (because step() returned false), but now we step up two steps using two step_up() calls. QED

<br>
The second (tail) recursion above can be turned into an iteration, as follows:
<pre>
func step_up()
{
    while not step() {
        step_up();
    }
}
</pre>

=={{header|11l}}==
{{trans|Python}}

=== Iterative ===
<syntaxhighlight lang="11l">F step_up1()
   V deficit = 1
   L deficit > 0
      I step()
         deficit--
      E
         deficit++</syntaxhighlight>

=== Recursive ===
<syntaxhighlight lang="11l">F step_up2()
   L !step()
      step_up2()</syntaxhighlight>

=={{header|ActionScript}}==
===Iterative===
<syntaxhighlight lang="actionscript">function stepUp()
{
	var i:int = 0;
	while(i < 1)
		if(step())i++;
		else i--;
}</syntaxhighlight>
===Recursive===
<syntaxhighlight lang="actionscript">function stepUp()
{
	if(!step())
	{
		stepUp();
		stepUp();
	}
}</syntaxhighlight>

=={{header|Ada}}==
<syntaxhighlight lang="ada">procedure Step_Up is
begin
   while not Step loop
      Step_Up;
   end loop;
end Step_Up;</syntaxhighlight>
The following is a test program simulating Step:
<syntaxhighlight lang="ada">with Ada.Numerics.Discrete_Random;
with Ada.Text_IO;

procedure Scaffolding is
   package Try is new Ada.Numerics.Discrete_Random (Boolean);
   use Try;
   Dice  : Generator;
   Level : Integer := 0;

   function Step return Boolean is
   begin
      if Random (Dice) then
         Level := Level + 1;
         Ada.Text_IO.Put_Line ("Climbed up to" & Integer'Image (Level));
         return True;
      else
         Level := Level - 1;
         Ada.Text_IO.Put_Line ("Fell down to" & Integer'Image (Level));
         return False;
      end if;
   end Step;
   
   procedure Step_Up is
   begin
      while not Step loop
         Step_Up;
      end loop;
   end Step_Up;
begin
   Reset (Dice);
   Step_Up;
end Scaffolding;</syntaxhighlight>
Sample output:
<pre>
Fell down to-1
Climbed up to 0
Fell down to-1
Climbed up to 0
Fell down to-1
Fell down to-2
Climbed up to-1
Climbed up to 0
Climbed up to 1
</pre>

=={{header|Aime}}==
{{trans|C}}
<syntaxhighlight lang="aime">void step_up(void)
{
    while (!step()) {
        step_up();
    }
}</syntaxhighlight>

=={{header|ALGOL 68}}==
{{trans|Ada}}

{{works with|ALGOL 68|Standard - no extensions to language used}}

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}} 

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8.8d.fc9.i386]}}
<syntaxhighlight lang="algol68">   PROC step up = VOID:
   BEGIN
      WHILE NOT step DO
         step up
      OD
   END # step up #;</syntaxhighlight>The following is a test program simulating step: <syntaxhighlight lang="algol68">
PROC scaffolding = VOID:
BEGIN
   INT level := 0;

   PROC step = BOOL:
   BEGIN
      IF random > 0.5 THEN
         level +:= 1;
         print(("Climbed up to",level, new line));
         TRUE
      ELSE
         level -:= 1;
         print(("Fell down to",level, new line));
         FALSE
      FI
   END # step #;

   PROC step up = VOID:
   BEGIN
      WHILE NOT step DO
         step up
      OD
   END # step up #;

   step up
END # scaffolding #;

scaffolding</syntaxhighlight>
Sample output:
<pre>
Fell down to         -1
Fell down to         -2
Climbed up to         -1
Climbed up to         +0
Climbed up to         +1
</pre>

=={{header|Arturo}}==

<syntaxhighlight lang="rebol">Position: 0

stepUp: function [].export:[Position][
    startPos: Position
    until -> step [
        Position = startPos + 1
    ]
]

step: function [].export:[Position][
    (0.5 > random 0 1.0)? [
        Position: Position - 1
        print ~"fall (|Position|)"
        false
    ][
        Position: Position + 1
        print ~"rise (|Position|)"
        true
    ]
]

stepUp</syntaxhighlight>

{{out}}

<pre>fall (-1)
fall (-2)
rise (-1)
rise (0)
fall (-1)
fall (-2)
rise (-1)
rise (0)
rise (1)</pre>

=={{header|AutoHotkey}}==
Recursive solution:
<syntaxhighlight lang="autohotkey">step_up()
{
    While !step()
       step_up()
}</syntaxhighlight>

=={{header|AWK}}==
<syntaxhighlight lang="awk">
function step_up() {
    while (!step()) { step_up() }
}
</syntaxhighlight>

=={{header|BASIC}}==
{{works with|QBasic}}
{{works with|Visual Basic}}

For many (most?) BASICs, <code>STEP</code> is a (case-insensitive) keyword, therefore the "step" function would need a different name -- in this example, "step1". (Also, for some BASICs -- notably those influenced by [[Microsoft]]'s [[QuickBASIC]] -- the underscore character ("'''_'''") is invalid inside subroutine names.)

<syntaxhighlight lang="qbasic">SUB stepup
    IF NOT step1 THEN stepup: stepup
END SUB</syntaxhighlight>

See also: [[#BBC BASIC|BBC BASIC]], [[#Liberty BASIC|Liberty BASIC]], [[#PureBasic|PureBasic]], [[#TI-83 BASIC|TI-83 BASIC]]

=={{header|BBC BASIC}}==
Recursive solution:
<syntaxhighlight lang="bbcbasic">      DEF PROCstepup
      IF NOT FNstep PROCstepup : PROCstepup
      ENDPROC</syntaxhighlight>

=={{header|C}}==
<syntaxhighlight lang="c">void step_up(void)
{
    while (!step()) {
        step_up();
    }
}</syntaxhighlight>

The following uses a variable and is a bit longer, but avoids a possible stack overflow by risking a probably less likely integer overflow instead:
<syntaxhighlight lang="c">void step_up(void)
{
    int i = 0;

    while (i < 1) {
        if (step()) {
            ++i;
        } else {
            --i;
        }
    }
}</syntaxhighlight>

=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">void step_up() {
    while (!step()) step_up();
}</syntaxhighlight>

=={{header|C++}}==
<syntaxhighlight lang="cpp">void step_up()
{
  while (!step()) step_up();
}</syntaxhighlight>

The following uses a variable and is a bit longer, but avoids a possible stack overflow:
<syntaxhighlight lang="cpp">void step_up()
{
  for (int i = 0; i < 1; step()? ++i : --i);
}</syntaxhighlight>

=={{header|Clojure}}==
First, some boilerplate.

<syntaxhighlight lang="lisp">;; the initial level
(def level (atom 41))

;; the probability of success
(def prob 0.5001)


(defn step
  []
  (let [success (< (rand) prob)]
    (swap! level (if success inc dec))
    success) )</syntaxhighlight>

=== Tail-recursive ===
The internal recursion uses a counter; see the function documentation.

<syntaxhighlight lang="lisp">(defn step-up1
  "Straightforward implementation: keep track of how many level we
   need to ascend, and stop when this count is zero."
  []
  (loop [deficit 1]
    (or (zero? deficit)
	(recur (if (step) (dec deficit)
		   (inc deficit)))) ) )</syntaxhighlight>

=== Recursive ===
This satisfies Chung-chieh's challenge to avoid using numbers. Might blow the stack as
''p'' approaches 0.5.

<syntaxhighlight lang="lisp">(defn step-up2
  "Non-tail-recursive. No numbers."
  []
  (if (not (step))
    (do (step-up2) ;; undo the fall
	(step-up2) ;; try again
	)
    true))</syntaxhighlight>

=={{header|Common Lisp}}==
<syntaxhighlight lang="lisp">(defun step-up ()
  (unless (step) (step-up) (step-up)))</syntaxhighlight>

=={{header|D}}==
The recursive version (note that "step_up" is equivalent to "step_up()" in D):
<syntaxhighlight lang="d">void step_up()
{
    while(!step)
        step_up;
}</syntaxhighlight>
The non-recursive version, using 1 variable:
<syntaxhighlight lang="d">void step_up_nr()
{
    for(uint i = 0; i < 1; step ? ++i : --i) {};
}</syntaxhighlight>
Test program:
<syntaxhighlight lang="d">import std.stdio;
import std.random;

int position;
bool step()
{
    bool r = rand() > (uint.max / 2);
    if(r)
        writefln("Climbed up to %d", ++position);
    else
        writefln("Fell down to %d", --position);
    return r;
}

void step_up()
{
    while(!step)
        step_up;
}

void main()
{
    rand_seed(0, 0); // to make it somewhat repeatable
    step_up;
}</syntaxhighlight>
Sample output:
<pre>Fell down to -1
Fell down to -2
Fell down to -3
Fell down to -4
Climbed up to -3
Fell down to -4
Climbed up to -3
Climbed up to -2
Climbed up to -1
Climbed up to 0
Climbed up to 1</pre>

=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}

Recursive version using no variables other than the Boolean returned by "Step"

<syntaxhighlight lang="Delphi">

{Recursive version}

procedure Step_Up;
begin
while not Step do Step_Up;
end;

</syntaxhighlight>

Iterative versions using one variable. 

<syntaxhighlight lang="Delphi">

{Iterative version}

procedure Step_Up;
var I: integer;
begin
while I<1 do
if Step then Inc(I) else Dec(I);
end;
</syntaxhighlight>

Functional example program

<syntaxhighlight lang="Delphi">
var Position: integer;

function Step(Memo: TMemo): boolean;
begin
Result:=Random(2)=1;
if Result then Inc(Position)
else Dec(Position);
If Result then Memo.Lines.Add(Format('Climbed up to %d', [Position]))
else Memo.Lines.Add(Format('Fell down to %d', [Position]));
end;


procedure StepUp(Memo: TMemo);
begin
while not Step(Memo) do StepUp(Memo);
end;


procedure ShowStairClimb(Memo: TMemo);
begin
Position:=0;
Randomize;
StepUp(Memo);
end;

</syntaxhighlight>
{{out}}
<pre>
Fell down to -1
Climbed up to 0
Fell down to -1
Climbed up to 0
Climbed up to 1
Elapsed Time: 4.600 ms.

</pre>

=={{header|E}}==

This is at first a very direct {{trans|Clojure}}

The problem framework:

<syntaxhighlight lang="e">var level := 41
var prob := 0.5001

def step() {
    def success := entropy.nextDouble() < prob
    level += success.pick(1, -1)
    return success
}</syntaxhighlight>

Counting solution:

<syntaxhighlight lang="e">def stepUpCounting() {
    var deficit := 1
    while (deficit > 0) {
        deficit += step().pick(-1, 1)
    }
}</syntaxhighlight>

Ordinary recursive solution:
<syntaxhighlight lang="e">def stepUpRecur() { 
    if (!step()) {
        stepUpRecur()
        stepUpRecur()
    }
}</syntaxhighlight>

Eventual-recursive solution. This executes on the vat ''queue'' rather than the stack, so while it has the same space usage properties as the stack-recursive version it does not use the stack which is often significantly smaller than the heap. Its return value resolves when it has completed its task.

<syntaxhighlight lang="e">def stepUpEventualRecur() {
    if (!step()) {
        return when (stepUpEventualRecur <- (),
                     stepUpEventualRecur <- ()) -> {} 
    }
}</syntaxhighlight>

Fully eventual counting solution. This would be appropriate for controlling an actual robot, where the climb operation is non-instantaneous (and therefore eventual):

[[Category:E examples needing attention]]
<syntaxhighlight lang="e">def stepUpEventual() {
    # This general structure (tail-recursive def{if{when}}) is rather common
    # and probably ought to be defined in a library.
  
    def loop(deficit) {
        if (deficit > 0) {
            return when (def success := step()) -> {
                loop(deficit + success.pick(-1, 1))
            }
        }
    }
    return loop(1)
}</syntaxhighlight>

=={{header|EchoLisp}}==
<syntaxhighlight lang="scheme">
(define (step-up) (while (not (step)) (step-up)))
;; checking this is tail-recusive :
step-up
   → (#λ null (#while (#not (step)) (#lambda-tail-call)))

;; Experimentation (not part of the task)
;; How much step calls to climb  1000 stairs ?
;; success is the robot success probability
(define (step) 
 (set! STEPS (1+ STEPS)) ;; count
 (< (random) SUCCESS)) ;; ->#t or #f

(define (climb stairs)
	(when (> stairs 0)  (step-up) (climb (1- stairs))))
	
(define (task  (stairs 1000))
	(for ((success (in-range 1 0 -5/100)))
	(set! SUCCESS success)
	(set! STEPS 0)
	(climb stairs)
	(writeln 'stairs stairs 'probability success 'steps STEPS)))
</syntaxhighlight>

{{out}}
<pre>
stairs     1000     probability     1         steps     1000    
stairs     1000     probability     19/20     steps     1062    
stairs     1000     probability     9/10      steps     1115    
stairs     1000     probability     17/20     steps     1207    
stairs     1000     probability     4/5       steps     1254    
stairs     1000     probability     3/4       steps     1305    
stairs     1000     probability     7/10      steps     1440    
stairs     1000     probability     13/20     steps     1542    
stairs     1000     probability     3/5       steps     1641    
stairs     1000     probability     11/20     steps     1865    
stairs     1000     probability     1/2       steps     2045    
stairs     1000     probability     9/20      steps     2177    
stairs     1000     probability     2/5       steps     2615    
stairs     1000     probability     7/20      steps     2769    
stairs     1000     probability     3/10      steps     3312    
stairs     1000     probability     1/4       steps     3963    
stairs     1000     probability     1/5       steps     5054    
stairs     1000     probability     3/20      steps     6573    
stairs     1000     probability     1/10      steps     9840    
stairs     1000     probability     1/20      steps     18689    

;; looks as if steps = stairs / success-probability
</pre>

=={{header|Elixir}}==
{{trans|Erlang}}
<syntaxhighlight lang="elixir">defmodule Stair_climbing do
  defp step, do: 1 == :rand.uniform(2)
  
  defp step_up(true), do: :ok
  defp step_up(false) do
    step_up(step)
    step_up(step)
  end
  
  def step_up, do: step_up(step)
end

IO.inspect Stair_climbing.step_up</syntaxhighlight>

=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
-module(stair).
-compile(export_all).

step() ->
    1 == random:uniform(2).

step_up(true) ->
    ok;
step_up(false) ->   
    step_up(step()),
    step_up(step()).

step_up() ->
    step_up(step()).
</syntaxhighlight>

=={{header|Euphoria}}==
<syntaxhighlight lang="euphoria">procedure step_up()
    if not step() then
        step_up()
        step_up()
    end if
end procedure</syntaxhighlight>

=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
let rec step_up() = while not(step()) do step_up()
</syntaxhighlight>
=={{header|Factor}}==
<syntaxhighlight lang="factor">: step-up ( -- ) step [ step-up step-up ] unless ;</syntaxhighlight>

=={{header|Forth}}==
Recursive. May exceed return stack unless compiler optimizes tail calls.
<syntaxhighlight lang="forth">: step-up   begin step 0= while recurse repeat ;</syntaxhighlight>
Counting. Avoids using a named variable.
<syntaxhighlight lang="forth">: step-up   -1 begin step if 1+ else 1- then ?dup 0= until ;</syntaxhighlight>

=={{header|Fortran}}==
{{trans|C++}}

{{works with|Fortran|90 and later}}
<syntaxhighlight lang="fortran">module StairRobot
  implicit none

contains

  logical function step()
    ! try to climb up and return true or false
    step = .true.     ! to avoid compiler warning
  end function step

  recursive subroutine step_up_rec
    do while ( .not. step() )
       call step_up_rec
    end do
  end subroutine step_up_rec

  subroutine step_up_iter
    integer :: i = 0
    do while ( i < 1 )
       if ( step() ) then
          i = i + 1
       else
          i = i - 1
       end if
    end do
  end subroutine step_up_iter

end module StairRobot</syntaxhighlight>

=={{header|FreeBASIC}}==
Since step is a statement modifier in FreeBASIC, we will use step_

Iterative version using one variable.
<syntaxhighlight lang="freebasic">Sub step_up()
    Dim As Integer i
    Do
        If step_() Then
            i += 1
        Else
            i -= 1
        End If
    Loop Until i = 1
End Sub</syntaxhighlight>

Recursive version.
<syntaxhighlight lang="freebasic">Sub step_up()
    While Not step_()
        step_up()
    Wend
End Sub</syntaxhighlight>

Demonstration program.
<syntaxhighlight lang="freebasic">Function step_() As Boolean
    If Int((Rnd * 2)) Then
        Print "Robot sube"
        Return True
    Else
        Print "Robot se cae"
        Return False
    End If
End Function
  
'recursive
Sub step_up()
    While Not step_()
        step_up()
    Wend
End Sub

step_up
Sleep</syntaxhighlight>


=={{header|Go}}==
38 bytes, no variables, no numbers.
<syntaxhighlight lang="go">func step_up(){for !step(){step_up()}}</syntaxhighlight>

=={{header|Groovy}}==
<syntaxhighlight lang="grovy">
class Stair_climbing{
static void main(String[] args){
}
static def step_up(){
    while not step(){
            step_up();
            }
}

}
</syntaxhighlight>

=={{header|Haskell}}==

In Haskell, stateful computation is only allowed in a monad. Then suppose we have a monad <code>Robot</code> with an action <code>step :: Robot Bool</code>. We can implement <code>stepUp</code> like this:

<syntaxhighlight lang="haskell">stepUp :: Robot ()
stepUp = untilM step stepUp

untilM :: Monad m => m Bool -> m () -> m ()
untilM test action = do
    result <- test
    if result then return () else action >> untilM test action</syntaxhighlight>

Here's an example implementation of <code>Robot</code> and <code>step</code>, as well as a <code>main</code> with which to test <code>stepUp</code>.

<syntaxhighlight lang="haskell">import Control.Monad.State
import System.Random (StdGen, getStdGen, random)

type Robot = State (Int, StdGen)

step :: Robot Bool
step = do
    (i, g) <- get
    let (succeeded, g') = random g
    put (if succeeded then i + 1 else i - 1, g')
    return succeeded

startingPos = 20 :: Int

main = do
    g <- getStdGen
    putStrLn $ "The robot is at step #" ++ show startingPos ++ "."
    let (endingPos, _) = execState stepUp (startingPos, g)
    putStrLn $ "The robot is at step #" ++ show endingPos ++ "."</syntaxhighlight>

=={{header|Icon}} and {{header|Unicon}}==

Icon (and Unicon) don't have boolean values.  Instead expressions (<i>all
expressions</i>) either <i>succeed</i> or they <i>fail</i>.  Control
structures respond to this success or failure.  Assuming that <tt>step()</tt>
is implemented in Icon (or Unicon) and fails only when the implementation in
another language returns <tt>false</tt>, then:
<syntaxhighlight lang="unicon">procedure step_up()
    return step() | (step_up(),step_up())
end</syntaxhighlight>

You can subtract a few more characters (and multiply the difficulty
of understanding) with:
<syntaxhighlight lang="unicon">procedure step_up()
    (|not step(), step_up())
end</syntaxhighlight>

=={{header|J}}==
'''Solution (Tacit):'''
<syntaxhighlight lang="j">step         =: 0.6 > ?@0:
attemptClimb =: [: <:`>:@.step 0:
isNotUpOne   =: -.@(+/@])

step_up=: (] , attemptClimb)^:isNotUpOne^:_</syntaxhighlight>
Note that <code>0:</code> is not a number but a verb (function) that returns the number zero irrespective of its argument(s). And, arguably, infinity is not any specific number. And, finally, <code>step</code> is presumed to pre-exist in the task description. Therefore the above solution for <code>step_up</code> could validly be said to meet the restrictions of no variables or numbers.

J's verbs (functions) always take an argument. J programmers use verbs which ignore their arguments (e.g. <code>step</code> and <code>attemptClimb</code>) to serve as verbs which "do not take an argument".

'''Solution (Explicit):'''
<syntaxhighlight lang="j">step_upX=: monad define           NB. iterative
  while. -. +/y do. y=. y , _1 1 {~ step 0 end.
)

step_upR=: monad define           NB. recursive (stack overflow possible!)   
   while. -. step'' do. step_upR'' end.
)</syntaxhighlight>

'''Example usage:'''
<syntaxhighlight lang="j">   step_up ''            NB. output is sequence of falls & climbs required to climb one step.
_1 1 _1 _1 1 1 1
   +/\ _1 1 _1 _1 1 1 1  NB. running sum of output (current step relative to start)
_1 0 _1 _2 _1 0 1
   +/\ step_up ''        NB. another example
_1 _2 _3 _2 _3 _2 _1 _2 _3 _4 _3 _2 _3 _2 _3 _2 _3 _2 _1 _2 _1 _2 _1 0 1</syntaxhighlight>


Another approach might be:

<syntaxhighlight lang="j">keepTrying=: (, {: - _1 ^ step)^:({. >: {:)^:_</syntaxhighlight>

Here, the argument is the number of the starting step and the result is a list of the numbers of each visited step including the initial and final steps.  For example:

<syntaxhighlight lang="j">   keepTrying 2
2 1 0 1 2 3
   keepTrying 3
3 2 3 2 3 2 3 4
   keepTrying 4
4 5</syntaxhighlight>

=={{header|Java}}==
{{trans|C++}}
<syntaxhighlight lang="java">public void stepUp() {
  while (!step()) stepUp();
}</syntaxhighlight>
The following uses a variable and is a bit longer, but avoids a possible stack overflow:
<syntaxhighlight lang="java">public void stepUp(){
  for (int i = 0; i < 1; step() ? ++i : --i);
}</syntaxhighlight>

=={{header|jq}}==
{{works with|jq|1.4}}

Since jq is a purely functional language, we need to keep track of time explicitly. This can be done using a clock that ticks the time:
<syntaxhighlight lang="jq">def tick: .+1;</syntaxhighlight>
To model the robot's success and failure, we shall assume a sufficiently large array of 0/1 values is available.
To avoid problems with modeling infinite time, we will pad the array with 1s if necessary.
<syntaxhighlight lang="jq">def random: [0, 0, 0, 1, 0, 1, 1, 0];</syntaxhighlight>

"step" returns true or false based on the current time (the input) and the value of "random":
<syntaxhighlight lang="jq">def step:
  random as $r
  | if . >= ($r|length) then true else ($r[.] == 1) end ;</syntaxhighlight>

We can now define step_up:
<syntaxhighlight lang="jq">def step_up:
  if step then tick
  else tick | step_up | step_up
  end;</syntaxhighlight>
Now we can start the simulation at time 0; step_up will then emit the number of "step" attempts that have been made to achieve success:
<syntaxhighlight lang="jq">0 | step_up</syntaxhighlight>
{{out}}
<syntaxhighlight lang="sh">$ jq -n -f stair-climbing_puzzle.jq
11</syntaxhighlight>
===Tail Call Optimization===
To take advantage of jq's TCO (available in versions of jq after the release of Version 1.4), the step_up
function must be tail-recursive and have arity 0.  This can be
achieved by providing [time, goal] as the input as follows:
<syntaxhighlight lang="jq">def tco_step_up:
  .[0] as $time | .[1] as $goal
  | if $goal == 0 then $time
    else
       if $time|step then $goal - 1 else $goal + 1 end
       | [ ($time|tick), .] | tco_step_up
    end ;</syntaxhighlight>
The simulation can then be started as follows:
<syntaxhighlight lang="jq">[0,1] | tco_step_up</syntaxhighlight>

=={{header|Julia}}==
As specified, shorter and fewer numbers preferred. It may be supposed that the robot would reach the bottom of any steps well before blowing the stack to reboot.
<syntaxhighlight lang="julia">
step_up() = while !step() step_up() end
</syntaxhighlight>
Here is an example to test the code with a step that has a 1/3 failure rate:
<syntaxhighlight lang="julia">
step() = (b = rand([true,true,false]); println(b); b)
step_up()
</syntaxhighlight>
{{output}}
<pre>
julia>  step_up()
true

julia>  step_up()
true

julia>  step_up()
false
true
true
</pre>

=={{header|Kotlin}}==
{{trans|D}}
<syntaxhighlight lang="scala">// version 1.2.0

import java.util.Random

val rand = Random(6321L) // generates short repeatable sequence
var position = 0

fun step(): Boolean {
    val r = rand.nextBoolean()
    if (r)
        println("Climbed up to ${++position}")
    else
        println("Fell down to ${--position}")
    return r
}

fun stepUp() {
    while (!step()) stepUp()
}

fun main(args: Array<String>) {
    stepUp()
}</syntaxhighlight>

{{out}}
<pre>
Fell down to -1
Fell down to -2
Climbed up to -1
Climbed up to 0
Fell down to -1
Climbed up to 0
Fell down to -1
Climbed up to 0
Climbed up to 1
</pre>

=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">'This demo will try to get the robot to step up
'Run it several times to see the differences; sometimes the robot falls
'quite a ways before making it to the next step up, but sometimes he makes it
'on the first try

result = Stepp.Up()

Function Stepp.Up()
    While Not(Stepp())
        result = Stepp.Up()
    Wend
End Function

Function Stepp()
    Stepp = Int((Rnd(1) * 2))
    If Stepp Then
        Print "Robot stepped up"
    Else
        Print "Robot fell down"
    End If
End Function</syntaxhighlight>

=={{header|Logo}}==
Recursive.
<syntaxhighlight lang="logo">to step.up
  if not step [step.up step.up]
end</syntaxhighlight>
Constant space (fully tail-recursive).
<syntaxhighlight lang="logo">to step.up [:n 1]
  if :n=0 [stop]
  (step.up ifelse step [:n-1] [:n+1])
end</syntaxhighlight>

=={{header|Lua}}==

<syntaxhighlight lang="lua">
function step_up()
    while not step() do step_up() end
end
</syntaxhighlight>

=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">StepUp[] := If[!Step[], StepUp[]; StepUp[]]</syntaxhighlight>

=={{header|MATLAB}}==
<syntaxhighlight lang="matlab">function step_up()
    while ~step()
        step_up();
    end</syntaxhighlight>

=={{header|Nim}}==
One liner (yes it is possible in Nim).
<syntaxhighlight lang="nim">proc stepUp = (while not step(): stepUp())</syntaxhighlight>

=={{header|OCaml}}==
<syntaxhighlight lang="ocaml">let rec step_up() =
  while not(step()) do
    step_up()
  done
;;</syntaxhighlight>

=={{header|Oz}}==
Recursive solution:
<syntaxhighlight lang="oz">proc {StepUp}
   if {Not {Step}} then
      {StepUp}  %% make up for the fall
      {StepUp}  %% repeat original attempt
   end
end</syntaxhighlight>
Might lead to a stack overflow because the first call to <code>StepUp</code> is not in tail position.

Iterative solution:
<syntaxhighlight lang="oz">proc {StepUp}
   Level = {NewCell 0}
in
   for until:@Level == 1 do
      if {Step} then Level := @Level + 1
      else Level := @Level - 1
      end
   end
end
</syntaxhighlight>
Oz has arbitrary large integers. So if the robot is very unlucky, the contents of the <code>Level</code> variable will fill up all the memory and the program will fail. I believe this problem needs infinite memory to be solved for all cases.

=={{header|PARI/GP}}==
<syntaxhighlight lang="parigp">step_up()=while(!step(),step_up())</syntaxhighlight>

=={{header|Pascal}}==
Recursive solution:
<syntaxhighlight lang="pascal">procedure stepUp;
begin
  while not step do
    stepUp;
end;</syntaxhighlight>

=={{header|Perl}}==
<syntaxhighlight lang="perl">sub step_up { step_up until step; }</syntaxhighlight>

=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
 <span style="color: #008080;">procedure</span> <span style="color: #000000;">step_up</span><span style="color: #0000FF;">()</span>
     <span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">do</span> <span style="color: #000000;">step_up</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
 <span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<!--</syntaxhighlight>-->

=={{header|PicoLisp}}==
<syntaxhighlight lang="picolisp">(de stepUp ()
   (until (step1)  # ('step1', because 'step' is a system function)
      (stepUp) ) )</syntaxhighlight>

=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">function StepUp
    {
    If ( -not ( Step ) )
        {
        StepUp
        StepUp
        }
    }
 
#  Step simulator for testing
function Step
    {
    If ( Get-Random 0,1 )
        {
        $Success = $True
        Write-Verbose "Up one step"
        }
    Else
        {
        $Success = $False
        Write-Verbose "Fell one step"
        }
    return $Success
    }
 
#  Test
$VerbosePreference = 'Continue'
StepUp</syntaxhighlight>
{{out}}
<pre>VERBOSE: Fell one step
VERBOSE: Fell one step
VERBOSE: Up one step
VERBOSE: Fell one step
VERBOSE: Fell one step
VERBOSE: Up one step
VERBOSE: Up one step
VERBOSE: Up one step
VERBOSE: Fell one step
VERBOSE: Up one step
VERBOSE: Up one step</pre>

=={{header|Prolog}}==
The robot code is very short
<syntaxhighlight lang="prolog">step_up :- \+ step, step_up, step_up.</syntaxhighlight>
	
The test program keeps track of the level in a dynamic predicate. 
<syntaxhighlight lang="prolog">:- dynamic level/1.
		
setup :-
	retractall(level(_)),
	assert(level(1)).
		
step :- 
	level(Level),
	random_between(0,3,N),
	(
		N > 0 -> 
			succ(Level, NewLevel), format('Climbed up to ~d~n', NewLevel)
		; 
			succ(NewLevel, Level), format('Fell down to ~d~n', NewLevel)
	),
	retractall(level(Level)),
	assert(level(NewLevel)),
	N > 0. % Fail if 0 because that is a non step up.</syntaxhighlight>
{{out}}
<pre>
?- setup, between(1,10,_), step_up, fail.
Climbed up to 2
Climbed up to 3
Climbed up to 4
Climbed up to 5
Fell down to 4
Climbed up to 5
Climbed up to 6
Fell down to 5
Climbed up to 6
Climbed up to 7
Climbed up to 8
Fell down to 7
Climbed up to 8
false.

?-
</pre>

=={{header|PureBasic}}==
Iterative version using one variable.
<syntaxhighlight lang="purebasic">Procedure step_up()
  Protected i
  Repeat: If _step(): i + 1: Else: i - 1: EndIf: Until i = 1
EndProcedure</syntaxhighlight>
Recursive version. Stack may overflow as probability of a fall approaches or exceeds 50%.
<syntaxhighlight lang="purebasic">Procedure step_up()
  While Not _step()
    step_up()
  Wend 
EndProcedure</syntaxhighlight>
Demonstration program.
<syntaxhighlight lang="purebasic">Global level

Procedure _step()
  If Random(1) ;equal chance of stepping up or falling down
    level + 1
    PrintN("Climbed up to " + Str(level))
    ProcedureReturn #True
  Else
    level - 1
    PrintN("Fell down to " + Str(level))
    ProcedureReturn #False
  EndIf 
EndProcedure
  
;recursive
Procedure step_up()
  While Not _step()
    step_up()
  Wend 
EndProcedure

If OpenConsole()
  PrintN("Begin at level: " + Str(level))
  step_up()
  PrintN("*** Now at level: " + Str(level))
   
  Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
  Input()
  CloseConsole()
EndIf</syntaxhighlight>
Sample output:
<pre>Begin at level: 0
Fell down to -1
Climbed up to 0
Fell down to -1
Climbed up to 0
Climbed up to 1
*** Now at level: 1</pre>

=={{header|Python}}==

=== Iterative ===
<syntaxhighlight lang="python">def step_up1():
  """Straightforward implementation: keep track of how many level we
     need to ascend, and stop when this count is zero."""
  deficit = 1
  while deficit > 0:
    if step():
      deficit -= 1
    else:
      deficit += 1</syntaxhighlight>

=== Recursive ===
This satisfies Chung-chieh's challenge to avoid using numbers. Might blow the stack as
''p'' approaches 0.5.

<syntaxhighlight lang="python">def step_up2():
  "No numbers."
  while not step():
    step_up2() # undo the fall</syntaxhighlight>

=={{header|Quackery}}==

<syntaxhighlight lang="quackery">[ step if done recurse again ] is step-up</syntaxhighlight>

=={{header|R}}==

The step() function described would not be idiomatic R, since it would
require using the global assignment operator to get the side effect.
<syntaxhighlight lang="r">step <- function() {
    success <- runif(1) > p
    ## Requires that the "robot" is a variable named "level"
    level <<- level - 1 + (2 * success)
    success
}</syntaxhighlight>

===Recursive Solution=== 

<syntaxhighlight lang="r">stepUp <- function() {
    while(! step()) {
        stepUp()
    }
}</syntaxhighlight>

===Iterative Solution===

<syntaxhighlight lang="r">stepUpIter <- function() {
    i <- 0
    while ( ! i) {
        i <- i - 1 + (2 * step())
    }
}</syntaxhighlight>

Example output:
<pre>
> p <- 0.25
> level <- 1
> print(level)
[1] 1
> stepUp()
> print(level)
[1] 2
> stepUpIter()
> print(level)
[1] 3
</pre>

=={{header|Racket}}==
<syntaxhighlight lang="racket">#lang racket
(define p 0.5001)
(define (step)
  (> p (random)))

(define (step-up n)
  (cond ((zero? n) 'done)
        ((step) (step-up (sub1 n)))
        (else (step-up (add1 n)))))

(step-up 1)</syntaxhighlight>

=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>sub step_up { step_up until step; }</syntaxhighlight>

=={{header|REBOL}}==
<syntaxhighlight lang="rebol">REBOL [
    Title: "Stair Climber"
    URL: http://rosettacode.org/wiki/Stair_Climbing
]

random/seed now

step: does [random/only reduce [yes no]]

; Iterative solution with symbol stack. No numbers, draws a nifty
; diagram of number of steps to go. This is intended more to
; demonstrate a correct solution:

step_up: func [/steps s] [
	either not steps [
		print "Starting up..."
		step_up/steps copy [|]
	][
		while [not empty? s][
			print ["    Steps left:" s]
			either step [remove s][append s '|]
		]
	]
]

step_up  print ["Success!" crlf]

; Recursive solution. No numbers, no variables. "R" means a recover
; step, "+" means a step up.

step_upr: does [if not step [prin "R " step_upr  prin "+ " step_upr]]

step_upr  print ["Success!" crlf]

; Small recursive solution, no monitoring:

step_upt: does [if not step [step_upt step_upt]]

step_upt  print "Success!"</syntaxhighlight>

Output:

<pre>Starting up...
    Steps left: |
    Steps left: | |
    Steps left: |
Success!

R R + R R R R R R R + + R + + + + + + R + R R + R + R + R + + + Success!

Success!</pre>

=={{header|REXX}}==
<syntaxhighlight lang="rexx">step_up:           do  while \step();   call step_up
                   end
          return</syntaxhighlight>

=={{header|Ring}}==
<syntaxhighlight lang="ring">
stepup()

func stepup
     n = 0
     while n < 1
           if stp() n=n+1 else n= n-1 ok
           see n + nl
     end

func stp
     return 0
</syntaxhighlight>

=={{header|Ruby}}==
<syntaxhighlight lang="ruby">def step_up
  start_position = $position
  step until ($position == start_position + 1)
end

# assumptions about the step function:
# - it maintains the current position of the robot "as a side effect"
# - the robot is equally likely to step back as to step up
def step
  if rand < 0.5
    $position -= 1
    p "fall (#$position)" if $DEBUG
    return false
  else
    $position += 1
    p "rise (#$position)" if $DEBUG
    return true
  end
end

$position = 0
step_up</syntaxhighlight>
Sample run:
<pre>$ ruby -d stair.climbing.rb
"fall (-1)"
"rise (0)"
"fall (-1)"
"rise (0)"
"fall (-1)"
"fall (-2)"
"rise (-1)"
"rise (0)"
"rise (1)"</pre>

=={{header|Run BASIC}}==
<syntaxhighlight lang="runbasic">
result = stepUp()
 
Function stepUp()
    While Not(stepp())
        result = stepUp()
    Wend
End Function
 
Function stepp()
	stepp = int((Rnd(1) * 2))
	print "Robot stepped "+word$("up down",stepp+1)
End Function
</syntaxhighlight>

=={{header|Rust}}==
<syntaxhighlight lang="rust">fn step_up() {
	while !step() {
		step_up();
	}
}</syntaxhighlight>

=={{header|SAS}}==

<syntaxhighlight lang="sas">
%macro step();
	%sysfunc(round(%sysfunc(ranuni(0))))
	%mend step;
</syntaxhighlight>

===Recursive===
<syntaxhighlight lang="sas">
%macro step_up();

	%if not %step %then %do;
		%put Step Down;
		%step_up;
		%step_up;
		%end;
	%else %put Step Up;

	%mend step_up;

%step_up;
</syntaxhighlight>

===Iterative===
<syntaxhighlight lang="sas">
%macro step_up();

	%do %while (not %step);
		%put Step Down;
		%step_up;
		%end;
	%put Step Up;

	%mend step_up;
</syntaxhighlight>



Sample Output:
<pre>
Step Down
Step Down
Step Down
Step Up
Step Down
Step Down
Step Up
Step Up
Step Up
Step Up
Step Up
</pre>

=={{header|Scala}}==
Simple recursive solution:

<syntaxhighlight lang="scala">def stepUp { while (! step) stepUp }</syntaxhighlight>

Non-recursive solution which almost gets away with not having named variables:

<syntaxhighlight lang="scala">def stepUp {
  def rec: List[Boolean] => Boolean = step :: (_: List[Boolean]) match {
    case true :: Nil => true
    case true :: false :: rest => rec(rest)
    case other => rec(other)
  }
  rec(Nil)
}</syntaxhighlight>

=={{header|Scheme}}==
<syntaxhighlight lang="scheme">(define (step-up n-steps)
  (cond ((zero? n-steps) 'done)
        ((step) (step-up (- n-steps 1)))
        (else (step-up (+ n-steps 1)))))</syntaxhighlight>

=={{header|Seed7}}==
<syntaxhighlight lang="seed7">const proc: step_up is func
  begin
    while not doStep do
      step_up;
    end while;
  end func;</syntaxhighlight>

=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func step_up() {
    while (!step()) {
        step_up();
    }
}</syntaxhighlight>

=={{header|Smalltalk}}==
{{works with|GNU Smalltalk}}

The following uses a block closure and the recursive solution which consumes stack until successful.
<syntaxhighlight lang="smalltalk">Smalltalk at: #stepUp put: 0.
stepUp := [ [ step value ] whileFalse: [ stepUp value ] ].</syntaxhighlight>

=={{header|Standard ML}}==

<syntaxhighlight lang="sml">
(*
 * val step : unit -> bool
 * This is a stub for a function which returns true if successfully climb a step or false otherwise.
 *) 
fun step() = true

(*
 * val step_up : unit -> bool
 *)
fun step_up() = step() orelse (step_up() andalso step_up())
</syntaxhighlight>

Alternate version:
<syntaxhighlight lang="sml">fun step() = true

fun step_up() = while step() = false do step_up()
</syntaxhighlight>

=={{header|Swift}}==
<syntaxhighlight lang="swift">func step_up() {
  while !step() {
    step_up()
  }
}</syntaxhighlight>

The following uses a variable and is a bit longer, but avoids a possible stack overflow:
<syntaxhighlight lang="swift">func step_up() {
  for var i = 0; i < 1; step()? ++i : --i { }
}</syntaxhighlight>

=={{header|Tcl}}==
The setup (note that <code>level</code> and <code>steps</code> are not used elsewhere, but are great for testing…)
<syntaxhighlight lang="tcl">set level 41
set prob 0.5001
proc step {} {
    global level prob steps
    incr steps
    if {rand() < $prob} {
	incr level 1
	return 1
    } else {
	incr level -1
	return 0
    }
}</syntaxhighlight>
===Iterative Solution===
All iterative solutions require a counter variable, but at least we can avoid any literal digits...
<syntaxhighlight lang="tcl">proc step-up-iter {} {
    for {incr d} {$d} {incr d} {
	incr d [set s -[step]]; incr d $s
    }
}</syntaxhighlight>
===Recursive Solution===
This is the simplest possible recursive solution:
<syntaxhighlight lang="tcl">proc step-up-rec {} {
    while {![step]} step-up-rec
}</syntaxhighlight>

=={{header|TI-83 BASIC}}==
TI-83 BASIC doesn't have functions (only subroutines), so a variable must be used as the return value for <code>prgmSTEP</code>. Set <code>A</code> to <code>1</code> before calling to display the offset from the stair it was called from (store in D). Set <code>B</code> to <code>1</code> to pause after each attempt. <code>C</code> is the return variable for <code>prgmSTEP</code>. <code>D</code> is the stair it is on (only used for display, and not used if <code>A</code> isn't <code>1</code>).

<code>prgmSTEP</code>:
<syntaxhighlight lang="ti83b">If rand>.5:Then
0→C
Disp "FALL"
If A=1:Then
D-1→D
Disp D
End
Else
1→C
Disp "CLIMB"
If A=1:Then
D+1→D
Disp D
End
End
If B=1
Pause</syntaxhighlight>

<code>prgmSTEPUP</code>:
<syntaxhighlight lang="ti83b">prgmSTEP
While C=0
prgmSTEPUP
prgmSTEP
End</syntaxhighlight>

=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "random" for Random
import "./fmt" for Conv

var rand = Random.new(1268) // generates short repeatable sequence
var position = 0

var step = Fn.new {
    var r = Conv.itob(rand.int(2))
    if (r) {
        position = position + 1
        System.print("Climbed up to %(position)")
    } else {
        position = position - 1
        System.print("Fell down to %(position)")
    }
    return r
}

var stepUp // recursive
stepUp = Fn.new {
    while (!step.call()) stepUp.call()
}

stepUp.call()</syntaxhighlight>

{{out}}
<pre>
Fell down to -1
Fell down to -2
Climbed up to -1
Climbed up to 0
Fell down to -1
Climbed up to 0
Climbed up to 1
</pre>

=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">proc Step_up;           \Iterative version
int I;
[I:= 0;
while I<1 do
        if Step then I:= I+1
        else I:= I-1;
];

proc Step_up;           \Recursive version
while not Step do Step_up;</syntaxhighlight>

=={{header|zkl}}==
According to Leon P Smith in the referenced LTU thread:

This version consumes stack space proportional to the number of steps it needs to go up, as opposed to the number of steps it attempts. This is a substantial difference if the probability of success is only somewhat greater than or equal to 1/2.
<syntaxhighlight lang="zkl">fcn step{  } // add code to return Bool
fcn stepUp{ while(not step()){ self.fcn() } }</syntaxhighlight>
You could also use "stepUp" instead of self.fcn, self.fcn seems a little clearer and makes it easier to refactor.

An example step function:
{{trans|D}}
<syntaxhighlight lang="zkl">var position=0;
fcn step(){  //-->0|1
   r:=(0).random(2);	// 0 or 1
   if(r) println("Climbed up to ",position+=1);
   else  println("Fell down to ", position-=1);
   r
}
stepUp();</syntaxhighlight>
{{out}}
<pre>
Fell down to -1
Climbed up to 0
Fell down to -1
Fell down to -2
Climbed up to -1
Climbed up to 0
Climbed up to 1
</pre>