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

Writing Recursive Functions

As mentioned in a previous post, a recursive function is a function that calls itself. This post will focus on writing recursive functions.The logic behind the function is pretty intuitive but I have found knowing where to start when writing the function to be challenging.   Danny gave me some really helpful tips for handling recursive function and with some practice, I was able to come about my own way.

When writing recursive codes, I always start with a base case that does not require recursion. I choose a base case based on the task I'm trying to do(and what I need to know). I then split the more complicated cases into pieces the base case can handle.

For example, the function below calculates the sum of the elements in a list.
 The simplest cases will be an empty list and a list of a single length.  In those cases the function will simply return 0 or the element of the list its self. I need to know the elements of the list so I can add them. Splitting the list into individual elements lets me know the elements so i can add them.

def summed_list(L:list) ->int:
'''Returns the sum of the elements of a list. If empty list, returns zero.'''
#note this function does not need to be done recursively

if L ==[]: #base case1
    return 0

elif len(L) ==1: #base case 2
    return L[0]

else:
    return summed_list(L[0:1]) + summed_list(L[1:len(L)]) #split complicated cases into case base case can handle i.e. single length list

If I wanted to calculate the sum of a nested list, I need to know if the element is itself a list so I can handle that. The base case here then must be when it is not a list(simplest). When it is not a nested list, I need to find each element and add them to another list that will be summed. If it is a list, iterate through that list as well as per the base case.

def summed_nested_list(L:list)->int:
'''Returns the sum of the element in a possibly nested list. If empty, returns zero.'''
   
return sum([summed_nested_list(x) if isinstance(x,list) else x for x in L])

So far, creating base cases based on the task and splitting the rest of the problem into chunks the base case can handle has made it a lot easier to write recursive codes.

Any other suggestions?
P.Jiggly