[HaBo]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class StairsClimbing {

	public static void main(String[] args) {
		Solver sv = new StairsClimbing().new Solver(4);
		System.out.println("Anzahl Möglichkeiten: "+ sv.getSolutionCount());
		System.out.println("Lösungen: "+ sv.getSolutions());
	}

	class Solver {

		private List<String> solutions = null;

		public Solver(int stairsCount) {
			this.solutions = new ArrayList<String>();
			this.doIt(stairsCount, prepareString(stairsCount));
		}

		private String prepareString(int stairsCount) {
			char[] array = new char[stairsCount];
			Arrays.fill(array, '1');
			return String.valueOf(array);
		}

		private void doIt(int pos, String stairs) {
			for(int i=pos; i>1; i--)
				doIt(i-2, stairs.substring(0,i-2) +"2"+ stairs.substring(i));
			solutions.add(stairs);
		}

		public String getSolutions() {
			Collections.reverse(solutions);
			String resultString = Arrays.toString(solutions.toArray());
			return resultString.substring(1, resultString.length()-1);
		}
		
		public int getSolutionCount() {
			return solutions.size();
		}

	}

}

Anzahl Möglichkeiten: 5
Lösungen: 1111, 211, 121, 112, 22

def step(n,steps_before):
    global stufen
    if n + 1 <= stufen:
        step(n + 1, steps_before + str(1))
    if n + 2 <= stufen:
        step(n + 2, steps_before + str(2))
    if n == stufen:
        global counter
        print steps_before
        counter += 1

counter = 0
stufen = int(raw_input("Wieviele Stufen gibt es?"))
step(0,"")
print "Ways: " + str(counter)

(define (treppe n stufen)
  (cond
    ((> stufen n) (+ (treppe (+ n 1) stufen) (treppe (+ n 2) stufen)))
    ((= stufen n) 1)
    ((< stufen n) 0)))

#include <iostream>

using namespace std;
int treppe( int stufe );
    int stufen;
    char* pointer;
    int counte;
    int moeglichkeiten;
int main( )
{
    // Eingabe:
    cout << "Treppenstufen: ";
    cin >> stufen;
    treppe( stufen );
    cout << "Moeglichkeiten: " << moeglichkeiten;
    delete [] pointer;
    return 0;
}
int treppe( int stufe ) {
    counte++;
    if ( stufe == stufen ) { // Am Anfang wird der char array für die lösung erstellt
    pointer = new char[stufen];
    }
    if ( stufe-2>-1 ) { // Wenn die stufenanzahl -2 nicht ins minus geht rekursion
        pointer[counte] = '2';
        counte = treppe(stufe-2); 
    }
    if ( stufe-1>-1 ) { // Wenn die Stufenzahl -1 nicht ins minus geht: rekursion
        pointer[counte] = '1';
        counte = treppe(stufe-1);
    }
    if ( stufe < 1 ) { // Wenn eine Lösung gefunden wurde ausgeben.
        for( int i=1; i < counte; i++) {
            cout << pointer[i] << " ";
        }
        cout << endl;
        moeglichkeiten++;
    }
        return counte-1; // Einen Schritt zurück gehen
}

fac 0 = 1
fac n = product [1..n]

n `binom` k = fac n `quot` (fac k * fac (n-k))

treppe :: Integer -> Integer
treppe n = sum [(n - 2*k + k) `binom` k | k <- [0..n `quot` 2]]

import Control.Monad.Fix
treppe n = fix ((1:) . scanl (+) 1) !! n

                                  
def moeglichkeiten(n):
    ergebnis = 0
    global muenzen
    for    muenze in muenzen:
    if muenze == n:
            ergebnis +=    1
    if muenze < n:
            global posibilities
            ergebnis += posibilities[n - muenze]
    return ergebnis
posibilities = []
posibilities.append(0)
muenzen    = [1,2]#,5,10,20,50,100,200]                                            
for i in range(1,2001):
    posibilities.append(moeglichkeiten(i))
    print str(i) + ': '+ str(posibilities[i])

treppe :: Integer -> [[Integer]]
treppe 0 = [[]]
treppe 1 = [[1]]
treppe n = [a:b | a <- [1,2], b <- treppe (n - a)]

*Main> length (treppe 20)
10946
*Main> length (treppe 25)
121393
*Main> length (treppe 30)
1346269
*Main> treppe 4
[[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]]