How can I reimplement this recursive function?

Question

So I'm trying to solve a puzzle and I came across this code. I can't figure out what the output would be and any attempts to run it result in a "reached the maximum amount of recursion" error. Sorry in advance for the goofy variable names.

How can I modify this to achieve the same output, without the recursion error? The initial numbers I'm passing are 13379446(arg 1) and 5(arg 2).

import sys

num1 = int(sys.argv[1])
num2 = int(sys.argv[2])

def doot(num1, num2):
    print num1
    print num2
    doritos = 0
    if num2 > num1:
        pass
    else:
        if num2 == 0:
            print "if"
            doritos = 1
        else:
            if num2 == num1:
                doritos = 1 
            else:
                wew = doot(num1 - 1, num2 - 1)
                doritos = wew
                wew = doot(num1 -1, num2)
                doritos = doritos + wew

    print doritos

Well, this function is one of four. I need to reimplement this so I can get it to run alongside the other functions. The output of all the functions combined will be a flag I'm trying to get. — Asa Hunt, Nov 29 '15 at 18:40
yes but what is the expected output? What is this trying to do? Without knowing that I can only suggest you build a dictionary (outside the function) to hold values during calculations as this is the standard fix for recursion depth issues (if that's your only issue as it runs with say `doot(3,1)`. — LinkBerest, Nov 29 '15 at 18:51
I don't know what the expected output should be besides a number. The challenge is tracing a value through the code without it running. Sorry this isn't super helpful. — Asa Hunt, Nov 29 '15 at 18:57
In the above code, `doot` doesn't return a value. Should `print doritos` be `return doritos` perhaps? — saulspatz, Nov 29 '15 at 20:08
This appears to be a badly written [nCr function](http://stackoverflow.com/questions/4941753/is-there-a-math-ncr-function-in-python) — Stuart, Nov 29 '15 at 21:16

score 2 · Answer 1 · answered Nov 29 '15 at 20:44

Let me get you started. I'm assuming that doritos is supposed to be the return value, that is, that the code should say return dortitos instead of print doritos. Also, I'm completely ignoring the line print if.

Now what do we know? Looking at the code we see that

doot(x,y) = 0 if y > x
doot(x,0) = 1
doot(x,x) = 1 and
doot(x,y) = doot(x-1,y-1) + doot(x-1,y) otherwise

So we want to figure out the value of doot(x+h,x) where h > 0. Start with the simplest case, h=1. We already know that doot(1,0)=1, so

doot(2,1) = doot(1,0)+doot(1,1) = 1+1 = 2
doot(3,2) = doot(2,1)+doot(2,2) = 2+1 = 3

and now it's easy to guess that

doot(x+1,x)=x+1 for all x>= 0.

t's also easy to prove this by induction, if you're so inclined.

So now, work out some examples when h=2, and figure out the formula for doot(x+2,x). Then figure out the formula for doot(x+3,x) and so on, until you're ready to guess the the formula for doot(x+h,x)

score 1 · Answer 2 · answered Nov 29 '15 at 20:01

Okay, I overhauled your code to use a dictionary (values) and a queue.

import sys

num1 = int(raw_input("num1: "))
num2 = int(raw_input("num2: "))

def doot(num1, num2):
    print num1
    print num2
    doritos = 0
    n1 = num1
    n2 = num2

    values = {}
    queue = [(num1,num2)]

    while queue:
        num1,num2 = queue.pop()
        #print queue
        #print values

        if (num1,num2) not in values:
            if num1 >= num2:
                if num2 == 0:
                    #print "if"
                    #doritos = 1
                    values[(num1,num2)] = 1
                else:
                    if num2 == num1:
                        #doritos = 1
                        values[(num1,num2)] = 1
                    else:
                        #wew = doot(num1 - 1, num2 - 1)
                        #doritos = wew
                        #wew = doot(num1 -1, num2)
                        #doritos = doritos + wew

                        if (num1-1,num2-1) in values and (num1-1,num2) in values:
                            values[(num1,num2)] = values[(num1-1,num2-1)] + values[(num1-1,num2)]
                        else:
                            queue.append((num1,num2))

                        if (num1-1,num2) not in values:
                            queue.append((num1-1,num2))

                        if (num1-1,num2-1) not in values:
                            queue.append((num1-1,num2-1))

    #print values

    doritos = values[(n1,n2)]

    print doritos
    return doritos

doot(num1,num2)

In essence, I use the queue to keep track of the sums I don't have yet. If both of the descendants of (num1,num2) are in the dictionary, then I put it in the dictionary with the sum of their values. Otherwise, I put either or both descendant that's not in the dictionary on the queue along with itself. The other times that I don't put (num1,num2) back on the queue are when num1 == num2 or num2 == 0, in which cases I put them in the dictionary with value 1. At the end, I return the value in the dictionary that corresponds to the original inputted numbers.

Now, a word of caution: this code is horribly inefficient. I just had to reboot my computer because I tried the inputs you gave in the question, and it gobbled up all of the available RAM. So, you should instead consider what exactly is being done with the recursion, and figure out how to work forwards from the base cases instead of backwards from the input. That task, I will leave to you.

score 1 · Answer 3 · edited May 23 '17 at 12:07

Your code is a recursive implementation of a combination function, which calculates the number of combinations of k distinct elements that can be drawn from a set of n elements.

A tidied up version of your function would look like this (note I have removed all the print statements and ensured that the function returns something - otherwise it won't work at all).

def doot(n, k):
    if n < k:
        return 0
    if k == 0 or n == k:
        return 1
    return doot(n - 1, k - 1) + doot(n - 1, k)

This works fine for small values of n and k. A faster version that doesn't rely on recursion uses factorials, as shown in this answer.

import math

def nCr(n, r):
    f = math.factorial
    return f(n) / f(r) / f(n - r)

However, calculating the factorial of 13379446 still takes a long time and may not be accurate because the result is so huge. My system hangs when I try it. The other answer to the same question appears to work better.

How can I reimplement this recursive function?

3 Answers3