Convert recursive function into a for loop and while loop

Question

I need to convert

def aRecursive(n):
    if n is 1:
        return 3
    else:
        return 2 * aRecursive(n-1) + 5

into a for loop and a while loop. I can't seem to wrap my mind around the process. The original function for these loops are:

a(1) = 3
a(n) = 2 * a(n-1) + 5

An answer and explanation would help out immensely.

Answer 1

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.

Answer 2

One possible for loop:

def a(n):
    answer = 3

    for i in range(n - 1):
        answer = answer * 2 + 5

    return answer

A possible while loop, though I don't particularly like using a while here:

def a(n):
    answer = 3

    while n > 1:
        answer = answer * 2 + 5
        n -= 1

    return answer

Note that neither of these answers (nor your original code) handle an n less than 1.

Explanation

a(1) = 3
a(n) = 2 * a(n - 1) + 5

So if you were to compute a(5), there are two reasonable approaches. One is to write out something recursive:

a(5) = 2 * a(4) + 5

Then compute a(4):

a(4) = 2 * a(3) + 5

so a(5) is now:

a(5) = 2 * (2 * a(3) + 5) + 5

You can continue this process until you don't have any references to a anymore, and then you can just do arithmetic.

The non-recursive way would be to count up:

a(1) = 3
a(2) = 2 * a(1) + 5  =  2 *  3 + 5  =  11
a(3) = 2 * a(2) + 5  =  2 * 11 + 5  =  27
a(4) = 2 * a(3) + 5  =  2 * 27 + 5  =  59
a(5) = 2 * a(4) + 5  =  2 * 59 + 5  =  123

This way, you start with 3 and then at each step, multiply by 2 and add 5 to obtain the next number. Just stop when you reach the n you were trying to compute the function of.

This second (non-recursive) method is how the for and while loops above work.