Saturday, 30 November 2013

Reading and Understanding Recursive Functions

Writing a recursive code is one thing but understanding someone else's code can be really confusing. This is something I struggled with on Term Test 1. I saw the first question, the several lines of code doing something funky, tried to make sense of it all but realised "Aint nobody got time for that".  After the exam I got some useful tips from Danny and I realised I was confusing my self.

I had already figured out what the base case was doing but each time I called the recursive function in my mind, I started ALL the way from the base case and worked up to the current call. This was wasting a lot of time and was unnecessary as I already knew what the base case produced.Now when I see a recursive code, I calculate the value of the base case and input that into each call. Likewise for the previous call.

For example, in Term Test 1
def s(n: int) -> tuple:
if n == 1:
    return (1, 1)
else:
    return min([(2 * s(n - i)[0] + 2**i - 1, i) for i in range(1,n)]) #upper limit of range not evaluated

s(1) returns (1,1)

When s(2) is called, the for loop evaluates the expression  (2 * s(1)[0]+ 2**(1-1),1 )
I already know that s(1) is (1,1) therefore s(1)[0] is 1 and the whole expression evaluates to (3,1)

When s(3) is called the first run of the for loop evaluates the expression (2 * s(2)[0] + 2**(1-1),1)
I already know that s(2) is (3,1) therefore s(2)[0] is 3 and the whole expression evaluates to (7,1)

Plugging the previously calculated run of the recursive code keeps things from getting unnecessarily complicated.This has helped me node get lost in the code.
Any other tips to keep your sanity when reading recursive codes?

P.Jiggly


No comments:

Post a Comment