How to return an incremented variable to next recursion call on the recursion stack?-CodePudding

So I am answering a question where we are given a flight of stairs that we need to climb and some target height. We are told the maximum number of steps we can take with each step. And we are asked to return the number of ways we can reach this target height, using recursion.

let's say that target height is 3, and the max steps is 2. Then the solution would be 3, since we can take the following steps #1,1,1 #1,2 and #2,1 to reach the target height.

Here is my code below:

def staircaseTraversal(height, maxSteps):
    numberOfWays = 0
    staircaseTraversalHelper(height, maxSteps, 0, 0)
    if numberOfWays:
        return numberOfWays
    return -1


def staircaseTraversalHelper(height, maxSteps, currentHeight, numberOfWays):
    for step in range(1, maxSteps 1):
        newHeight = currentHeight   step
        if newHeight == height:
            return numberOfWays   1
        elif newHeight < height:
            staircaseTraversalHelper(height, maxSteps, newHeight, numberOfWays)

My question is regarding updating the numberOfWays when we hit such a point where the current step we are on (newHeight) is equal to the target height, and we increment the numberOfWays by 1, I am then struggling to return this numberOfWays to the next recursion call on the recursion stack!

At the moment I am doing return numberOfWays 1 - but I don't think this is correct. I also tried incrementing numberOfWays by 1, then simply breaking out of the for loop, then returning nothing to get to the next recursion call in the recursion stack, but this doesn't seem to work either.

Also, it would be great if I could get feedback on the set up of my overall recursive solution, as I am quite new to the ideas, albeit I do understand it quite comprehensively.

CodePudding user response：

This is a simple solution to your answer, instead of adding a new argument "currentHeight", you can do it like this

def staircaseTraversal(height, maxSteps):
    numbersOfWays = 0
    for step in range(1, maxSteps 1):
        if height == step:
            numbersOfWays  =1
            break
        elif height < step:
            break
        else:
            numbersOfWays  = staircaseTraversal(height -step, maxSteps)
    return numbersOfWays
print(staircaseTraversal(3,2))

CodePudding user response：

I think you can do something like below. Here, height argument means the "remaining height", so I subtract steps for the recursive calls. Note that you may also use sum to reduce the number of lines.

def staircaseTraversal(height, maxSteps):
    if height == 0:
        return 1
    if height < 0:
        return 0

    out = 0
    for step in range(1, min(height, maxSteps)   1):
        out  = staircaseTraversal(height - step, maxSteps)
    return out

staircaseTraversal(3, 2)
# 3