4
$\begingroup$

I have to show whether a program containing only if-else statements but no loops is able to calculate the following type of functions: $f^n(x)$. The function $f$ is applied $n$ times to $x$, so I guess this is a recursive function.

How can I prove that formally?

$\endgroup$

migrated from stackoverflow.com Jun 20 '13 at 1:19

This question came from our site for professional and enthusiast programmers.

  • 1
    $\begingroup$ It's not necessarily recursive. You could use, e.g., a for loop to solve it iteratively. Thinking about iteration might suggest an answer to your problem. $\endgroup$ – jpaugh Jun 18 '13 at 17:39
  • $\begingroup$ Do you mean that if/else is the only type of flow-control statement? Because you'll probably need some method invocations, at least. $\endgroup$ – Ryan Jun 18 '13 at 17:47
  • $\begingroup$ My question is: Can I create a recursive function by only using if-else statements? No loops. Only if-then-else stuff. $\endgroup$ – Nicolas Jun 18 '13 at 17:49
  • $\begingroup$ If $n$ is fixed and $f$ itself is not recursive and does not use a while loop, the target function does not require recursion. Please edit the question to focus and either that or what you ask in your comment. $\endgroup$ – Raphael Jun 21 '13 at 6:22
2
$\begingroup$

IMHO the cleanest way to have a recursive calculation function is to ONLY use a if-else. Since there are usually only two main conditions in a recursive function( 1 - base case met, 2 - base case not met) it is only logical to only have two condition checks. The if checks for the base case, if the base case has not been reached else does calculations and sends the new recursive call. Below is some pseudo code for a recursive function for the example you provided.

int recursiveFunction(int n,int x)
{
    if(n==1)
    {
       return x;
    }
    else
    { 
       x=x*x//or whatever work is being done
       return (n-1,x);
    }
}
$\endgroup$
2
$\begingroup$

I'm not sure entirely what you mean. Are you allowed method invocations? If so you can provide this example:

def apply_multiple(f, x, n):
  if n == 0:
    return x
  else:
    return f(apply_multiple(f, x, n-1))

If you're talking about writing that particular function without ANY flow control other than if statements, you can't. Consider the line number you're currently on. This can only increase, so for a finite program there are only a finite number of states it can be in. This isn't going to work if n can be an arbitrary number.

$\endgroup$
2
$\begingroup$

If a program doesn't include any loop, recursion or equivalent construct, then it cannot express recursive computations.

In order to write a formal proof, you'd need to define your language formally. “Equivalent construct” can include some exotic things such as parallel execution, exception handlers, higher-order functions (leading to fixpoint combinators), meta-execution facilities (eval), etc. that let recursion in through a backdoor.

Suppose that a language contains only the following constructs: constants, assignments, sequence (do a then do b), functions operating on base types (but not functions taking functions as arguments), conditionals (if (x == y)), some primitives on base types (e.g. +, *). Then the execution of the program takes a time that is at most exponential, and in particular bounded, in the size of the program (the unit of time is an elementary expression, e.g. x := y takes one unit, x := y + z takes two units). In a nutshell, function application at most multiplies the complexity of the function by the complexity of the program, and the rest is linear.

Since this language can only express bounded-time computations, it cannot express all recursive programs (and in fact it cannot even express all primitive recursive programs).

$\endgroup$
-1
$\begingroup$

In Elixir, this would be as easy as

def nthApply(f, x, n) do
  if n < 1 do
    x
  else
    nthApply(f, f.(x), n-1)
  end
end
$\endgroup$
  • 1
    $\begingroup$ Isn't your answer covered by robbie_c's? $\endgroup$ – xskxzr Mar 7 at 12:11
  • $\begingroup$ Maybe. I'm just anal about doing every recursion tail recursively. $\endgroup$ – Erle Czar Mantos Mar 8 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.