Recursive Program

Question

Write a recursive program called waysToClimb that takes a positive integer representing

a number of stairs and prints (i) each unique way to climb a staircase of that height,

taking strides of one or two stairs at a time, and (ii) the total number of ways. Do

not use any loops. Output each way to climb on its own line, using a 1 to indicate a

small stride of 1 stair, and a 2 two indicate a large stride of 2 stairs.

The order in which you report each way to climb is important. Design your recursive

method to produce the order shown in the example.

Example:

Enter the number of stairs to climb (positive integer): 4

[1, 1, 1, 1]

[1, 1, 2]

[1, 2, 1]

[2, 1, 1]

[2, 2]

Total number of ways = 5

Answer 1

class ArtemisL

{

public static void main(String args[])

{

(new ArtemisL()).waysToClimb(4, 0, "[");

}

public void waysToClimb(int n, int position, String result)

{

if (n == position)

{

int index = result.lastIndexOf(",");

if (index != -1)

{

result = result.substring(0, index) + "]";

System.out.println(result);

}

}

else if (n > position)

{

waysToClimb(n, position + 1, result + "1, ");

waysToClimb(n, position + 2, result + "2, ");

}

}

}