Recursion without Referencing and Assignment

user_4443051 0
Viewed 3806

The problem is given a recursive function in python (or similar), can it be re-written it so that it doesn't reference itself. I've made a simple example which applies to the problem. Of course, making it a non-recursive function is not allowed. It must still do the same recursion process.

def fact(n):
  if n == 0:
    return 1
  return n * fact(n - 1)

It's also equivalent to a short-hand.

fact = lambda n: 1 if n == 0 else n * fact(n - 1)

In the example, I shouldn't call fact inside the function definition.

Edit:

Additional constraints: Assignments must not be necessary for the solution to work.

One solution (from the comments) without the additional constraint is to create two functions a and b which call each other alternately and do factorial effevtively. This is not allowed because it requires that you assign two functions in two variables.

A quick example of a function that doesn't need assignment is

f = lambda x: x + 1

For it to execute on the arugment 55, I could just write

(lambda x: x + 1)(55)

So assignment was not necessary.

Any hints on this? Or am I being tricked to an impossible problem?

recursion python
2 Answers

You can use something like lambda calculus to avoid assignment and self reference, replacing both with access to an argument of an anonymous function. For example:

fact = (lambda f: f(f))(lambda f: (lambda n: n*f(f)(n-1) if n else 1))

Tested in Ideone.

Some details below for further background.

I know lambda calculus is famous for being a powerful (Turing complete) yet minimalistic “programming language”. It only uses identifiers for variables, which can be either bound (pretty much function arguments) or unbound (mostly relevant when talking about parts of an expression). So it felt like a good starting point.

The canonical way to express recursion in lambda calculus is using a fixed point combinator. While that combinator can be expressed naively in Python syntax, eager evaluation leads to infinte recursion.

The code at https://rosettacode.org/wiki/Y_combinator#Python mentioned in comments avoids this infinite recursion by delaying one of the recursive calls till the function actually gets called. But I would prefer leaving detailed explanation of that approach to a separate answer.

What is the core idea of expressing recursion in lambda calculus? Passing a function as an argument to itself. So I started with this:

lambda f: f(f)  # λ f.f f

I need to pass that function another function that takes a function as a value. Like lambda f: …. And the result of that call should be a function that should take an n as an argument to compute the factorial. My first approximation was thinking of f itself as an expression for the recursive call, so I had this first:

(lambda f: f(f))(lambda f: (lambda n: n*f(n-1) if n else 1))

But then I realized this was wrong: f itself is not the recursive call, since f is the function that takes an argument f. So f(f) is the recursive call, leading to the solution I printed in the beginning.

user_14683660

This is most likely absolutely not what the question is about, but with some inspect/types magic you can reconstruct the function being called...

import types, inspect


def fact(n):
    frame = inspect.currentframe()
    fn = types.FunctionType(frame.f_code, frame.f_globals)

    if n == 0:
        return 1
    return n * fn(n - 1)


print(fact(10))
AKX_516850
Related