Write recursive pseudocode problem in python code

Question

I am having trouble to solve the problem below:

I am supposed to implement the pseudocode in python. h is just some given list. I have tried all kinds of stuff, most recently for example:

def _p_recursion(n,i):
    if n == 0:
        return h[n+i]

    for i in range(1,n+1):
        s = 0
        s = h[i] + _p_recursion(n-i,i)
    v.append(s)
    return s    

v=[]    
h =[0,3,11,56,4]

_p_recursion(2,0)

I know why it does not work but I am not able to come up with a solution. It feels like a pretty simple problem but I have been stuck with it for hours. I am not very experienced with recursive functions only really basic ones. I can't come up with one. Feels like the simplest way to come up with a solution must be to append all possible outputs of p(n) into an array and then one can easily find the maximum. For the values in the code above 11 is missing from the list v. Can anybody give me a hint how to fix this problem using python statements for, if, while...

Thanks in advance!

You should at least try doing this by yourself, post your code here and ask about specific problems you've encountered — konserw, Apr 05 '20 at 15:40

DarrylG · Accepted Answer · 2020-04-06T22:26:27.153

Code

def p(n):
  " Implements function shown in image "
  if n == 0:
    return 0

  # Finds the max of h[i] + p(n-i)
  # with p(n-i) found recursively
  # Gets access to h from the global namespace
  return max(h[i] + p(n-i) for i in range(1, n+1))

More explicit recursive function

   def p(n):
      " Implements function shown in image "
      if n == 0:
        return 0

      # Stores previous results in an array for formula
      # then computes max
      previous = []
      for i in range(1, n+1):
          previous.add(h[i] + p(n-i)) 
      return max(previous)

Test

h = range(10)

for i in range(len(h)):
  print(i, p(i))

Output

Performance

darrylg solution

def p_dg(n):
  " Implements function shown in image "
  if n == 0:
    return 0

  # Finds the max of h[i] + p(n-i)
  # with p(n-i) found recursively
  # Gets access to h from the global namespace
  return max(h[i] + p_dg(n-i) for i in range(1, n+1))

Poster (Karl) solution

def p(n,m):
    if n == 0:
        return 0

    for i in range(1,n+1):
        s = h[i] + p(n-i,m)
        m[n-1].append(s)

    return max(m[n-1])


def p_caller(n):
    if type(n) != int:
        return
    m =[] 
    for g in range(n):
        m.append([])

    return p(n,m)

darrylg solution with caching (memorization)

def p_cache(n, cache = {}):
  if n in cache:
    return cache[n]

  if n == 0:
    return 0

  cache[n] =  max(h[i] + p_cache(n-i) for i in range(1, n+1))

  return cache[n]

Timing (seconds)

darrylg method
time taken: 0.20136669999965306
Poster method (Karl)
time taken: 26.77383000000009
darrylg with memoization
time taken: 0.00013790000002700253

Thus Caching greatly improves performance.

Timing Code

import time
import random

# timing software allows timing recursive functions
# Source: https://stackoverflow.com/questions/29560643/python-counting-executing-time-of-a-recursion-function-with-decorator
def profile(f):
    is_evaluating = False
    def g(x):
        nonlocal is_evaluating
        if is_evaluating:
            return f(x)
        else:
            start_time = time.perf_counter()
            is_evaluating = True
            try:
                value = f(x)
            finally:
                is_evaluating = False
            end_time = time.perf_counter()
            print('time taken: {time}'.format(time=end_time-start_time))
            return
    return g

# darrylg method
@profile
def p_dg(n):
  " Implements function shown in image "
  if n == 0:
    return 0

  # Finds the max of h[i] + p(n-i)
  # with p(n-i) found recursively
  # Gets access to h from the global namespace
  return max(h[i] + p_dg(n-i) for i in range(1, n+1))

# Poster (Karl) method
def p(n,m):
    if n == 0:
        return 0

    for i in range(1,n+1):
        s = h[i] + p(n-i,m)
        m[n-1].append(s)

    return max(m[n-1])

@profile
def p_caller(n):
    if type(n) != int:
        return
    m =[] 
    for g in range(n):
        m.append([])

    return p(n,m)

# darrylg with caching (Memoization)
@profile
def p_cache(n, cache = {}):
  if n in cache:
    return cache[n]

  if n == 0:
    return 0

  cache[n] =  max(h[i] + p_cache(n-i) for i in range(1, n+1))

  return cache[n]

h = [random.randint(0, 100) for _ in range(18)]

l = 17
print('darrylg method')
p_dg(l)

print('Poster method (Karl)')
p_caller(l)

print('darrylg with memoization')
p_cache(l)

Thanks! I am trying to understand the last line "return max(h[i] + p(n-i) for i in range(1, n+1))" of the code. Is there any way one could write that part without the built in max() function? — Karl Karlsson, Apr 05 '20 at 20:23
@KarlKarlsson `range(1, n+1)` generates numbers from `1, 2,...n` (doesn' t include n+1). So this is similar to the return of max(h[1]+p(n-1), h[2]+p(n-2), ...h[n]+p[0]) to generate the value for p(n). Before returning it has to recursively compute p(0) to p(n-1) to fill in the formula. This would be inefficient but so in a practical system you would use a technique call "memorization" to make this recursive function more efficient. — DarrylG, Apr 05 '20 at 20:42
But still how would i write the code in an "inefficient" way, using only recursive calls? — Karl Karlsson, Apr 06 '20 at 09:37
@KarlKarlsson--my solution does "write the code in an inefficient way using only recursive alls". This is because it has the recursive compute `(h[i] + p(n-i) for i in range(1, n+1)` before computing the max. I'll update my answer with a more explicit recursive formula. — DarrylG, Apr 06 '20 at 11:21
I eventually found a way to solve this problem another way. See the code below: **def p(n,m): if n == 0: return 0 for i in range(1,n+1): s = h[i] + p(n-i,m) m[n-1].append(s) return max(m[n-1]) def p_caller(n): if type(n) != int: return m =[] for g in range(n): m.append([]) return p(n,m)** What is the time complexity for my solution vs yours? — Karl Karlsson, Apr 06 '20 at 20:04
@KarlKarlsson--will check, but first I'm getting a syntax error on `return m =[] `. Can you double-check this line in your code? — DarrylG, Apr 06 '20 at 20:20
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/211104/discussion-between-darrylg-and-karl-karlsson). — DarrylG, Apr 06 '20 at 22:26

Karl Karlsson · Answer 2 · 2020-04-06T20:39:53.997

I was not able to comment my code in the previous post so I am writing it here instead: (my Solution to problem)

def p(n,m):
    if n == 0:
        return 0

    for i in range(1,n+1):
        s = h[i] + p(n-i,m)
        m[n-1].append(s)
    return max(m[n-1])


def p_caller(n):
    if type(n) != int:
        return
    m =[] 
    for g in range(n):
        m.append([])
    return p(n,m)

I would never actually call p() only p_caller() DarrylG solution to problem:

def p(n):
    if n == 0:
        return 0

# Finds the max of h[i] + p(n-i)
# with p(n-i) found recursively
# Gets access to h from the global namespace
    return max(h[i] + p(n-i) for i in range(1, n+1))

What would the difference in worst case time complexity be between these methods and why?

Write recursive pseudocode problem in python code

2 Answers2

Test