Python exercise with functions, recursion and classes
I am doing an exercise in which I have to create a class that represents functions (written as lambda expressions) and several methods associated with them.
The ones I have written so far:
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 exp function creates the function k-1 times by itself. Now I have to write a recursive version of the specified function using the same "self" and "k" arguments. However, I'm having a hard time figuring out how this would work. In the original exp, I wrote that I had access to the original function "i" on all iterations, however when creating the recursive function, I lose access to the original function and each iteration only has access to the most recently linked function. So, for example, if I try to compose myself with myself a certain number of times, I get:
f= x+3 f^2= x+6 (f^2)^2= x+12
So we missed the function x + 9.
How do I get around this? Is there a way to preserve 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)
source to share
This is an exercise, so I won't give an answer.
In recursion, you want to do two things:
-
Define and check the "armed state" that tells you when to stop; and
-
Determine and calculate the "repetition ratio" that will tell 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 pretty obvious - it's the only conditional statement! And the recurrent relation is in the return statement.
For your exercise, things are a little less obvious, since the goal is to define function composition, not direct 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)). This directly indicates the state of protection and the recurrence relation:
The guard condition is that exp () only works for positive numbers. This is because exp (0) can return different things for different input types (what does exp (0) return when f = Func (lambda s: s + '!')?).
So check for exp (1) and let that condition be the original lambda.
Then when defining exp (n + 1) recursively, let it be the composition of your original lambda with exp (n).
You have a couple of things to consider: First, your class instance has data associated with it. This data will "move" with you in your recursion, so you don't need to recursively pass as many parameters. Second, you need to decide if Func.exp () should create a new Func (), or if it should modify an existing Func object. Finally, consider how you would write a hard-coded function Func.exp2()
that has just built what we would call Func.exp(2)
. This should give you an idea of your recurrent relationship.
Update
Based on some comments I feel like I should be showing this code. If you want your recursive function to modify an object self
instead of returning a new object, you need to "cache" the values from self
before they are changed, for example:
func = self.func
domain = self.domain
... recursive function modifies self.func and self.domain
source to share