Generate list of elements by recursion

Question

I have the following recurrence relation H(n) = 2*H(n-1) + 1, H(1) = 1. If i were to make a recursive function in python how might this look? I have attempted with the following, but it does not seem to work

def rec_func(N, n=0, H=[])
    if n == 1:
        return [1] + H
    else:

        return rec_fun(N-1, n+1, H)

I might be totally off, but any hint would be appreciated. It is supposed to return a list of the elements [H(1), H(2),...H(N)]

note that the n=0, H=[] in the constructor is obligatory. This is an excercise from my textbook "Numerical Analysis"

What output do you get with that code? Also, you are not making use of `N` anywhere in your computation. You are simply subtracting 1 from it and passing it in each iteration, but never actually using it. — koolahman, Sep 16 '19 at 13:03
Take care with that `H=[]` in your function header, as [default mutable arguments](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument) can lead to surprising behavior. It shouldn't be a problem as your code is now, since you never mutate H, but it's worth keeping in mind. — Kevin, Sep 16 '19 at 13:10
You mention H(0) in you expected output, but H(n) is not defined for n<1 — buran, Sep 16 '19 at 13:19
`note that the n=0, H=[] in the constructor is obligatory.` - well, throw away textbook that __requires__ mutable default argument. — buran, Sep 16 '19 at 13:21
@sn3jd3r As per your explanations H(0) is not defined - you don't know what it should return — buran, Sep 16 '19 at 13:22

Cyriaque Pin · Accepted Answer · 2019-09-16T13:30:21.980

6

If you want to make a recursive function just do :

def H(n):
    if n == 1:
        return 1
    else:
        return 2*H(n-1)+1

If you want the output to be a list you have to make something like :

def H_with_list(n, list_final):
    if n == 1:
        list_final.append(1)
        return list_final
    else:
        list_temp = H_with_list(n-1, list_final)
        list_final.append(2*list_temp[-1]+1)
        return list_final

Be careful because recursive function are time consuming, you should calculate H(n) and make it work with one line of code

edited Sep 16 '19 at 13:30

answered Sep 16 '19 at 13:22

Cyriaque Pin

108
7

4

`list` is built-in function. never use built-in functions, module names, etc. as variable names – buran Sep 16 '19 at 13:24

Dipen Dadhaniya · Answer 2 · 2019-09-16T13:21:38.820

2

Try this:

# h(n) = 2 * h(n - 1) + 1
# h(1) = 1

def get_h_series(n):
    if n == 1:
        # h(1) = 1
        return [1]
    else:
        # ans = [h(0), h(1), ..., h(n - 1)]
        ans = get_h_series(n-1)
        # Append h(n) which is 2 * h(n - 1) + 1.
        ans.append(2 * ans[-1] + 1)
        # [h(0), h(1), ..., h(n - 1), h(n)]
        return ans

print(get_h_series(5))

Output:

[1, 3, 7, 15, 31]

edited Sep 16 '19 at 13:21

answered Sep 16 '19 at 13:11

Dipen Dadhaniya

4,550
2
16
24

Note that strictly speaking H(n) is expected to return single number. Then they have to produce a list for all results for n = [1, n]. – buran Sep 16 '19 at 13:18
Thanks - the output is correct. I just edited the question a bit as the constructor needs the N, n and H. – sn3jd3r Sep 16 '19 at 13:21

Nafis Islam · Answer 3 · 2019-09-30T03:04:36.387

0

Something like this:

def rec_func(n=1, H=[]):
    if not H:
        H = [None] * (n+1)

    if n == 1:
        H[n] = 1
    else:
        H =  rec_func(n-1, H)
        H[n] = 2 * H[n-1] + 1

    return H 

H = rec_func(3)

print(H) // prints -> [None, 1, 3, 7]

edited Sep 30 '19 at 03:04

answered Sep 16 '19 at 13:25

Nafis Islam

1,483
1
14
34

score 0 · Answer 4 · answered Sep 16 '19 at 14:09

Here's another way that doesn't require lookups like temp[-1] as the computation is running

def main(n, a=1):
  if n<=1:
    return [a]
  else:
    return [a, *main(n-1, 2*a+1)]

print(main(10))
# [ 1, 3, 7, 15, 31, 63, 127, 511, 1023 ]

print(main(1))
# [1]

score -1 · Answer 5 · answered Sep 16 '19 at 13:36

While other answers will solve this problem recursively as you have asked for, it is worth mentioning that this problem is not too difficult or ugly to solve using iteration. If you want to use large values of n, your code is likely to fail with either a RuntimeError maximum recursion depth exceeded in comparison, or a stack overflow (heh). You can solve that by implementing it iteratively, like this for example:

def list_h_results(n):
    h_results = []
    for i in range(1, n+1):
        h_results.append(2 * h_results[-1] + 1)
    return h_results

I'm not saying do this for your exercise necessarily, but it's a consideration worth making in the future if implementing this kind of function in real code. Usually recursion is chosen for these types of problems because it is elegant and easier to understand, but I think in this case the iterative solution is just as easy to understand and avoids the potential problems associated with deep recursion.

Generate list of elements by recursion

5 Answers5