CODEWITHSUNDEEP
pythonooprecursion
user8134203
user8134203

Reputation:

Python Exercise involving functions, recursion and classes

I'm doing an exercise where I'm to create a class representing functions (written as lambda expressions) and several methods involving them.

The ones I've written so far are:

class Func():
    def __init__(self, func, domain):
        self.func = func
        self.domain = domain

    def __call__(self, x):
        if self.domain(x):
            return self.func(x)
        return None

    def compose(self, other):
        comp_func= lambda x: self.func(other(x))
        comp_dom= lambda x: other.domain(x) and self.domain(other(x))
        return Func(comp_func, comp_dom)

    def exp(self, k):
        exp_func= self
        for i in range(k-1):
            exp_func = Func.compose(exp_func, self)
        return exp_func

As you can see above, the function exp composes a function with itself k-1 times. Now I'm to write a recursive version of said function, taking the same arguments "self" and "k". However I'm having difficulty figuring out how it would work. In the original exp I wrote I had access to the original function "self" throughout all iterations, however when making a recursive function I lose access to the original function and with each iteration only have access to the most recent composed function. So for example, if I try composing self with self a certain number of times I will get:

f= x+3
f^2= x+6
(f^2)^2= x+12

So we skipped the function x+9.

How do I get around this? Is there a way to still retain access to the original function?

Update:

def exp_rec(self, k):
    if k==1:
        return self
    return Func.compose(Func.exp_rec(self, k-1), self)

Upvotes: 3

Views: 387

Answers (1)

aghast
aghast

Reputation: 15310

This is an exercise, so I won't provide the answer.

In recursion, you want to do two things:

  • Determine and check a "guard condition" that tells you when to stop; and

  • Determine and compute the "recurrence relation" that tells you the next value.

Consider a simple factorial function:

def fact(n):
    if n == 1:
        return 1

    return n * fact(n - 1)

In this example, the guard condition is fairly obvious- it's the only conditional statement! And the recurrence relation is in the return statement.

For your exercise, things are slightly less obvious, since the intent is to define a function composition, rather than a straight integer computation. But consider:

f = Func(lambda x: x + 3)

(This is your example.) You want f.exp(1) to be the same as f, and f.exp(2) to be f(f(x)). That right there tells you the guard condition and the recurrence relation:

The guard condition is that exp() only works for positive numbers. This is because exp(0) might have to return different things for different input types (what does exp(0) return when f = Func(lambda s: s + '!') ?).

So test for exp(1), and let that condition be the original lambda.

Then, when recursively defining exp(n+1), let that be the composition of your original lambda with exp(n).

You have several things to consider: First, your class instance has data associated with it. That data will "travel along" with you in your recursion, so you don't have to pass so many parameters recursively. Second, you need to decide whether Func.exp() should create a new Func(), or whether it should modify the existing Func object. Finally, consider how you would write a hard-coded function, Func.exp2() that just constructed what we would call Func.exp(2). That should give you an idea of your recurrence relation.

Update

Based on some comments, I feel like I should show this code. If you are going to have your recursive function modify the self object, instead of returning a new object, then you will need to "cache" the values from self before they get modified, like so:

func = self.func
domain = self.domain

... recursive function modifies self.func and self.domain

Upvotes: 2

Related Questions