请用递归和非递归两种方式实现爬楼梯问题，并分别说明各自的时间复杂度和空间复杂度。

回答思路

1. 能正确写出递归解法，并指出存在重复计算问题
2. 能正确写出非递归解法（如循环或动态规划），并说明时间复杂度为 O(n)
3. 能准确分析两种方法的时间复杂度和空间复杂度
4. 能说明递归改为迭代优化的思路（如记忆化或自底向上）