Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursion with dynamic arguments [duplicate]

This was an interview question which I haven't yet been able to figure out. Consider the following:

function recurse(a) {
    return function(b) {
        console.log(a + b);
    }
}

//This will log '5' in the console
recurse(2)(3);

Now I was asked to write a function that will take n number of arguments and work the same way by logging the final summation of the argument values. Meaning:

//This should log '13'
recurse(2)(3)(1)(7)

How can such a function be written? I have tried thinking over it in terms of recursion, dynamic arguments etc. But haven't been able to write down anything concrete.

like image 839
Rutwick Gangurde Avatar asked Jul 28 '16 11:07

Rutwick Gangurde


People also ask

How to make a recursive function more efficient?

Bottom-up. Sometimes the best way to improve the efficiency of a recursive algorithm is to not use recursion at all. In the case of generating Fibonacci numbers, an iterative technique called the bottom-up approach can save us both time and space.

Is recursion inefficient?

Recursive algorithms are often inefficient for small data, due to the overhead of repeated function calls and returns. For this reason efficient implementations of recursive algorithms often start with the recursive algorithm, but then switch to a different algorithm when the input becomes small.

Can recursion causes infinite loop?

Iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false; infinite recursion occurs if the recursion step does not reduce the problem in a manner that converges on the base case.

Can you have two base cases recursion?

A recursive implementation may have more than one base case, or more than one recursive step. For example, the Fibonacci function has two base cases, n=0 and n=1.


3 Answers

Here's the simplest version I could think of:

function add (a) {
  return function (b) {
    return b == null ? a : add(a+b);
  }
}

console.log( 
  add(2)(3)() 
);
console.log(
  add(10)(100)(1000)(4)() 
);

In es6, it's compact!

let add = a => b => b == null ? a : add(a+b);

Note

The trouble with your question is that a function can either return a Function or a Number. The following code:

let result = add(2)(3);

is equivalent to:

/*1*/ let partialResult = add(2);
/*2*/ let result = partialResult(3);

In line 1, add doesn't know whether it is being called with the last argument or not! In other words, it doesn't know whether partialResult should be a number, or a function that will be called with another argument.

Nina Scholz gives you a solution where partialResult will behave like a number when treated like a primitive, and like a function when called like a function. In my solution, partialResult always acts like a function, and returns a sum when called without an argument.

The first approach requires a language-specific mechanism for "behaving like a number" under certain conditions. If your interview was about JavaScript, it's the best approximation! But in a language-agnostic context, what you are asking for is impossible.

like image 110
A. Vidor Avatar answered Oct 20 '22 06:10

A. Vidor


You could return the function and implement toString and valueOf methods.

function recurse(x) {
    var sum = x;  

    function f(y) { 
        sum += y;
        return f;
    }; 
    f.toString = function () { return sum; }; // for expecting string, 1st log
    f.valueOf = function () { return sum; };  // for expecting number, 2nd log

    return f;
}

console.log(recurse(2)(3)(4));
console.log(recurse(2)(3) + recurse(4)(5));
console.log(recurse(2)(40) == 42);  // converts to expected type Number
console.log(recurse(2)(40) === 42); // checks type Function
like image 44
Nina Scholz Avatar answered Oct 20 '22 07:10

Nina Scholz


It is not requested that the recursion actually returns anything. It should just log.

And because the requirement is to log the final summation of the argument values, we can assume that it's perfectly fine to log the intermediate summations as well (unless it was explicitly forbidden in the full problem statement).

So, I suppose the interviewer would have accepted the following solution. It may actually be what he/she was expecting, given the initial source code.

function recurse(a) {
  console.log(a);
  return function(b) {
    return recurse(a + b);
  }
}

recurse(2)(3)(5)(7)

If you really want to display only the last summation, you can either:

  1. Cheat a little by using a console.clear() (not my preferred solution):

function recurse(a) {
  console.clear();
  console.log(a);
  return function(b) {
    return recurse(a + b);
  }
}

recurse(2)(3)(5)(7)
  1. Use a combination of clearTimeout() and setTimeout(). Here, we take advantage of the single-threaded nature of Javascript which prevents the callback from being executed until the expression is fully evaluated.

var t;

function recurse(a) {
  t && clearTimeout(t);
  t = setTimeout('console.log(' + a + ');', 0);
  return function(b) {
    return recurse(a + b);
  }
}

recurse(2)(3)(5)(7)
like image 2
Arnauld Avatar answered Oct 20 '22 05:10

Arnauld