How to return each recursive function call in Python?

Question

I might not be using the correct terminology, but I am rather new to programming (so forgive me if this is an easy search, I am not sure if I am using the correct keywords).

Let's say I have a recurrence relation:

f(0) = 2

f(x) = f(x-1) + 1 for x >= 1.

Now, let's say I want to program this relation using recursion in Python (2.7), but instead of returning just f(x), I want to return a list: [ f(x), f(x-1), ..., f(0) ].

I can easily program the recurrence relation to return f(10):

def my_fun(x):
    if x == 0:
        return 2
    else:
        return 1+my_fun(x-1)

However, I am at a loss as of how to return each function call without using a for loop.

Is there a way to do this?

EDIT: I would like to avoid using a for loop if possible.

Is not using a for loop one of your requirements? You did not make that clear. Also, could you return a list in the reverse order of the one you show; i.e. [f(0), f(1), ..., f(x)]? That would make more sense and is close to dynamic programming or memoization. — Rory Daulton
– Rory Daulton, Commented Sep 4, 2017 at 0:16
I am trying to avoid a for loop because I have noticed I use them "too much," even when not necessary. And yes, reverse order is fine. — amarsh
– amarsh, Commented Sep 4, 2017 at 0:22
@amarsh I don't understand your comment about for-loop. FYI, a for-loop is typically more efficient than recursion and therefore preferred. Recursion is ok sometimes and maybe you're not sensitive to the timing. Your stated reason - that you use for-loops too often - doesn't really make sense. — Brick
– Brick, Commented Sep 4, 2017 at 0:49
@Brick What I meant is that I already know how to solve it using a loop. I am trying to practice solving problems using different approaches and recursion is one of my weaker areas. At least, programming recursion, I have no issue with the concept thanks to my math background. Since I knew the problem could be solved with recursion, I wanted to figure out how to do it. — amarsh
– amarsh, Commented Sep 4, 2017 at 15:03

Anonta · Accepted Answer · 2017-09-04 00:25:31Z

1

You can return a list and use the last element to calculate the value in the previous call.

def my_fun(x):
    if x == 0:
        return [2]
    else:
        l = my_fun(x-1)
        l.append(l[-1] + 1) # since f(n-1) is in the last element

        return l

a = my_fun(5)

print(a)

answered Sep 4, 2017 at 0:25

Anonta

2,5402 gold badges17 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to return each recursive function call in Python?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related