def func(my_list, z):

    if z == len(my_list):
        return something
    else:
        # do something else
        return func(my_list, z+1)

z = someValue
print func(my_list, z)    

You should not use list as variable name.

Actually you should break the function down first:

A loop has a few parts:

1. the header, and processing before the loop. May declare some new variables

2. the condition, when to stop the loop.

3. the actual loop body. It changes some of the header's variables and/or the parameters passed in.

4. the tail; what happens after the loop and return result.

Or to write it out:

foo_iterative(params){
    header
    while(condition){
        loop_body
    }
    return tail
}

Using these blocks to make a recursive call is pretty straightforward:

foo_recursive(params){
    header
    return foo_recursion(params, header_vars)
}

foo_recursion(params, header_vars){
    if(!condition){
        return tail
    }

    loop_body
    return foo_recursion(params, modified_header_vars)
}

Et voilà; a tail recursive version of any loop. breaks and continues in the loop body will still have to be replaced with return tail and return foo_recursion(params, modified_header_vars) as needed but that is simple enough.

Going the other way is more complicated; in part because there can be multiple recursive calls. This means that each time we pop a stack frame there can be multiple places where we need to continue. Also there may be variables that we need to save across the recursive call and the original parameters of the call.

We can use a switch to work around that:

bar_recurse(params){
    if(baseCase){
        finalize
        return
    }
    body1
    bar_recurse(mod_params)
    body2
    bar_recurse(mod_params)
    body3
}


bar_iterative(params){
    stack.push({init, params})

    while(!stack.empty){
        stackFrame = stack.pop()

        switch(stackFrame.resumPoint){
        case init:
            if(baseCase){
                finalize
                break;
            }
            body1
            stack.push({resum1, params, variables})
            stack.push({init, modified_params})
            break;
        case resum1:
            body2
            stack.push({resum2, params, variables})
            stack.push({init, modified_params})
            break;
        case resum2:
            body3
            break;
        }
    }
}

Your recursive version is doing the backslide before checking that the height is reached. This check should happen between the forward rush and the backslide, not after the backslide.

Here is a correction, which also avoids the extra parameter:

def num_rushes(slope_height, rush_height_gain, back_sliding):
    if slope_height <= rush_height_gain:
        return int(slope_height > 0)
    return 1 + num_rushes(slope_height - rush_height_gain + back_sliding, 
                          0.95 * rush_height_gain, 0.95 * back_sliding)

Note the base case: if the slope_height is zero, no step has to be taken and 0 should be returned. In all other cases where the forward rush reaches the height, 1 should be returned.

I am going to offer a solution based on how functions are called. This solution is generic, in that you can use the same approach to convert any recursive function to an iterative one. It is theoretically possible but it seems no one talks about how. Since your function is easy, it is not hard to come up with a iterative one. But how about non-recursive post-order traversal of a binary tree? You can only do it on a case by case basis if you don't have a generic approach that I am going to present.

Here we go. First we need to write down your recursive version with a slight change to facilitate the conversion:

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
[start]:         # here we create a label; not python, only for converting
    if n == 1:
        return 3
    else:
        return 2 * f(n-1) + 5

Next we are going to convert two things: the function call and the return statements. The function call is basically 2 steps: push parameters and return address to stack and jump to the actual code. The return is basically pop parameters and jump to the saved address. So here we go:

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
[start]:         # here we create a label; not python, only for converting
    if n == 1:
        return 3
    else:
        push(n)       # push current parameter; since there is only one recursive function call in the body, we know where to return and there is no need to push the return address
        n = n-1       # the next level actual parameter is now n-1
        goto [start]  # we go to the code of the function which is the start of this same function
        return 2 * f(n-1) + 5  # we will never reach here... this line is where we need to return when any `return` statements is met

Next we will change the first return statements (the return 3):

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
[start]:         # here we create a label; not python, only for converting
    if n == 1:
        res = 3
        # for `return` we need to see if this is the top level or a inner recursive call
        if stack is empty: # we are in top level
            return res
        # hey we are in a recursive call, and we need to return to the code after `goto`, why not move these code here?
        else:
            n = pop()      # we pop the parameter saved
            # this line is where we need to return when any `return` statements is met
            return 2 * f(n-1) + 5
    else:
        push(n)       # push current parameter; since there is only one recursive function call in the body, we know where to return and there is no need to push the return address
        n = n-1       # the next level actual parameter is now n-1
        goto [start]  # we go to the code of the function which is the start of this same function

Then we will convert the return 2*f(n-1)+5:

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
[start]:         # here we create a label; not python, only for converting
    if n == 1:
        res = 3
        if stack is empty:
            return res
        else:
            [loop]:
            n = pop()      # we pop the parameter saved
            # begin conversion of return
            res = 2*res+5
            if stack is empty:
                return res;
            else:
                # we need to pop stack and jump to the same return, so we just jump to [loop]
                goto [loop]
    else:
        push(n)       # push current parameter; since there is only one recursive function call in the body, we know where to return and there is no need to push the return address
        n = n-1       # the next level actual parameter is now n-1
        goto [start]  # we go to the code of the function which is the start of this same function

Now the conversion is done, and we need to simplify this mess. First we should consider if a stack is really need. For this particular problem, every push just make n=n-1 and every pop makes n=n+1. So the stack is not really needed.

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
[start]:         # here we create a label; not python, only for converting
    if n == 1:
        res = 3
        if n == N:         # SAME as stack is empty
            return res     # really return
        else:
            [loop]:
            n = n+1       # WE JUST INCREASE N INSTEAD OF POP
            res = 2*res+5
            if n==N:      # SAME as stack is empty
                return res;
            else:
                goto [loop]
    else:
        # NO PUSH NEEDED
        n = n-1       # the next level actual parameter is now n-1
        goto [start]

The stack is eliminated, and we need to make these goto statements disappear. Notice the [start] label and goto [start] makes a loop, we just need to make them a 'while' loop:

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
    # we reverse the if n==1 and make it a condition in while
    while n != 1:
        # NO PUSH NEEDED
        n = n-1       # the next level actual parameter is now n-1
    # you soon noticed the above calculation is not needed at all, it just sets n = 1

    res = 3
    if n == N:
        return res
    else:
        [loop]:
        n = n+1
        res = 2*res+5
        if n==N:
            return res;
        else:
            goto [loop]

We optimized the first loop and replace them with n=1. And we need to make the second loop labeled by [loop] and goto [loop] disappear:

def f(N):
    n = N        # N is the top level parameter passed to this function
    res = None   # res is the result returned by this function
    n = 1        # the result of the first while loop

    res = 3
    if n == N:
        return res
    else:
        do:              # Python does not have do while, but it is straight forward to do this convert
            n = n+1
            res = 2*res+5
        while n!=N
        return res

We will soon notice that the first 4 statements can be combined and we remove all comments:

def f(N):
    n = 1
    res = 3
    if n == N:
        return res
    else:
        do:
            n = n+1
            res = 2*res+5
        while n!=N
        return res

We will reverse the if n==N statement:

def f(N):
    n = 1
    res = 3
    if n != N:
        do:
            n = n+1
            res = 2*res+5
        while n!=N
        return res
    else:
        return res

It is obvious that return res can be put on top level and the if n!=N and do/while loop can be combined to a single while loop:

def f(N):
    n = 1
    res = 3
    while n != N:
        n = n+1
        res = 2*res+5
    return res

This is the equivalent version of the original recursive function. Notice that I do not dig into this specific problem to come up with this version, I only deal with function call conversions. I suggest you go through the whole process on your own in your favorite text editor and it is kind of fun. You will find it is very mechanical and the only thing that requires some thought is the stack usage. Other techniques like "reverse if conditions" or "convert goto to structural loops" are quite easy.

It is also interesting to see that the iterative version is more efficient than the recursive one based only on the conversion process alone because: 1. we eliminate the use of the stack; 2. we eliminate a loop that decrease n to 1. We at least save some CPU cycles and stack storage.

You are actually right, the logic behind is the same and you can also apply while loop for e.g. Fibonacci sequence. Just the notation of recursion is usually shorter and more elegant.

Your code can be even simplified a bit and then you see that your solutions are kind of similar:

While loop:

Copydef countdown(n):
    while n > 0: # Step 1 -> check
        print(n)
        n = n-1 # Step 2  -> recursive call in while loop
    print('Blast off!') # Step 3 -> end ensured by Step 1

Recursion:

Copydef countdown(n):
    if n > 0: # Step 1 -> check
        print(n)  
        return countdown(n-1) # Step 2 -> recursive call of the countdown()
    else:
        print('Blast off!') # Step 3 -> end ensured by Step 1

Significant is that action n-1. You recursively act on a variable or object (Step 2) as long as your condition related to that variable/object is valid (Step 1).

def count(ls):
    if not ls:  # empty
        return 0
    return count(ls[1:]) + 1

Use it like this:

>>> find = [a, b, c, d]
>>> count(find)
4

how about this ?:

def fibonacci(n, a=0, b=1):
   if a >= n : return [a]
   return [a] + fibonacci(n,b,a+b)

[EDIT] Here's how it works:

The function progressively builds an array by adding one element [a] to the result of the next call to itself.

The first line allows it to stop when the target is reached. Without it, the second line of the function would keep calling itself and there would never be a result coming back from the recursion.

Because the parameters of a function are local to each call, the value of a and b in the second call are different from the previous ones.

If we follow the logic for fibonacci(7), we get:

1) fibonacci(n=7, a=0, b=1) ==> will return [0] + fibonacci(7,1,1).

2) fibonacci(n=7, a=1, b=1) ==> will return [1] + fibonacci(7,1,2).

3) fibonacci(n=7, a=1, b=2) ==> will return [1] + fibonacci(7,2,3).

4) fibonacci(n=7, a=2, b=3) ==> will return [2] + fibonacci(7,3,5).

5) fibonacci(n=7, a=3, b=5) ==> will return [3] + fibonacci(7,5,8).

6) fibonacci(n=7, a=5, b=8) ==> will return [5] + fibonacci(7,8,13).

7) fibonacci(n=7, a=8, b=13) ==> 8 >= 7 so the first line returns [8]

At that point there are no more recursive calls (the first line returns without calling the function again) and the return values start coming back up.

7) returns [8]

6) returns [5,8]

5) returns [3,5,8]

4) returns [2,3,5,8]

3) returns [1,2,3,5,8]

2) returns [1,1,2,3,5,8]

1) returns [0,1,1,2,3,5,8]

One way to think about recursive functions is to look only at the incremental work to be done on the result that would be produced by a prior parameter value. Most of the time this part of the logic applies backwards (i.e computing the end result based on a previous one). For example, a factorial can be thought of as the multiplication of a number with the factorial of the previous number.

This gives you the equivalent of the second line.

Once you have that down, all you need to decide is the condition that makes the recursion stop. Usually this corresponds to the smallest/simplest use case. For example, a factorial does not need to recurse when the number is less than 2 so the function can return 1 directly.

This gives you the equivalent of the first line.

As you can see in the above tracing, the function will proceed "forward" but actually ends up waiting for a result from itself (with different parameters) before being able to complete the process. This is how recursive functions work. The final result is typically built when the return values come back up from the stack of multiple self-calls.

Your fibonacci function is a bit trickier than a factorial because the series can only be computed from the original (0,1) values. Unlike the factorial, we don't have enough information to figure out the value of a and b based on the supplied parameter (n).

And, if you'd like to sink you teeth in cryptic code, here's a one line version:

def fibo(n,a=0,b=1):return [a]+fibo(n,b,a+b) if a < n else [a]

Here is a recursive version of this procedure, in python:

def cat(a,b):
  if a == b:
    return [a]
  else:
    return [a] + cat(a+1,b)

Another option is

def cat(a,b):
  if a == b:
    return [b]
  else:
    return cat(a,b-1) + [b]

These conversions are heavily geared toward this particular function. Here is a more general conversion, in the context of state machines without input (inputs can easily be added):

def run_my_algorithm(state = None):
  if state is None:
    state = initial_state
  if is_final_state(state):
    return extract_answer(state)
  else:
    state = next_state(state)
    return run_my_algorithm(state)

Hopefully the notation is self-explanatory.

Recursion is not intrinsically better or worse than loops - each has advantages and disadvantages, and those even depend on the programming language (and implementation).

Technically, iterative loops fit typical computer systems better at the hardware level: at the machine code level, a loop is just a test and a conditional jump, whereas recursion (implemented naively) involves pushing a stack frame, jumping, returning, and popping back from the stack. OTOH, many cases of recursion (especially those that are trivially equivalent to iterative loops) can be written so that the stack push / pop can be avoided; this is possible when the recursive function call is the last thing that happens in the function body before returning, and it's commonly known as a tail call optimization (or tail recursion optimization). A properly tail-call-optimized recursive function is mostly equivalent to an iterative loop at the machine code level.

Another consideration is that iterative loops require destructive state updates, which makes them incompatible with pure (side-effect free) language semantics. This is the reason why pure languages like Haskell do not have loop constructs at all, and many other functional-programming languages either lack them completely or avoid them as much as possible.

The reason why these questions appear so much in interviews, though, is because in order to answer them, you need a thorough understanding of many vital programming concepts - variables, function calls, scope, and of course loops and recursion -, and you have to bring the mental flexibility to the table that allows you to approach a problem from two radically different angles, and move between different manifestations of the same concept.

Experience and research suggest that there is a line between people who have the ability to understand variables, pointers, and recursion, and those who don't. Almost everything else in programming, including frameworks, APIs, programming languages and their edge cases, can be acquired through studying and experience, but if you are unable to develop an intuition for these three core concepts, you are unfit to be a programmer. Translating a simple iterative loop into a recursive version is about the quickest possible way of filtering out the non-programmers - even a rather inexperienced programmer can usually do it in 15 minutes, and it's a very language-agnostic problem, so the candidate can pick a language of their choice instead of stumbling over idiosyncracies.

If you get a question like this in an interview, that's a good sign: it means the prospective employer is looking for people who can program, not people who have memorized a programming tool's manual.

The reason why you are seeing the None is because you have a print inside your input:

input(print("Would you like to find the factorial of another non-negative integer? Y/N: "))

Remove that print

input("Would you like to find the factorial of another non-negative integer? Y/N: ")