search a sum of 2 numbers in an array with recurtion

[redroze]

hello folks,

I have an array of integers and I need to search if there's a combination of 2 numbers that resault a defined sum.
No loops or static variable are allowed.
Any suggestions?

cheers,
Elad.

[gerard4143]

hello folks,

I have an array of integers and I need to search if there's a combination of 2 numbers that resault a defined sum.
No loops or static variable are allowed.
Any suggestions?

cheers,
Elad.

You could try recursion.

[xavier666]

Strictly speaking, this problem is not recursive in nature.
What you can do is to let the function call itself (while traversing through the array) and with the help of some conditional operators check when the predefined sum is equal to the running sum inside the function.
But this is not recursion. This is just a function calling itself

[gerard4143]

O.K., try a 'quasi' recursion solution

[uskok]

The problem actually can be solved using real recursion.

The function would call itself, with a pointer to the array as an argument. On each subsequent call, the pointer would be incremented by one.
The base case is sending pointer to the last element of the array.

[xavier666]

O.K., try a 'quasi' recursion solution

LOL

uskok, what you're doing is just traversing with the help of recursion. But there is no doubt that the job will get done. But the actual problem is the summation of the problem.
For example, the first code is an example of true recursion

int true_recursion_factorial(int n)
{  
    if(n == 1)
        return 1;
    else if(n == 0)
        return 1;
    else
        return n * true_recursion_factorial(n - 1);
}

It treats memory as stack
This one is false recursion

answer = 1;     // global variable
int false_recursion_factorial(int n)
{
    if(n >= 1)
    {
        answer *= n;
        n -- ;
        false_recursion_factorial(n);
    }
    else if (n == 0)
        answer = 1;
    
    return  answer;
}

This one simply stores the answer in a place.
I can't explain the exact difference actually in writing to satisfy you. But i'm sure both of them are not equal.

[nezachem]

> I can't explain the exact difference actually in writing to satisfy you.

The difference is right here:
> answer *= n; If you look closely at your first example you will see that there's no assignments, not a single one. An assignment changes what is technically called a state. The truly recursive solution doesn't have the notion of state. It doesn't use assignments even for the local variables. In fact, a properly implemented functional (that is, recursive) language has no concept of a variable whatsoever.

BTW, uskok didn't give any implementation details. Until I see the code I wouldn't say if it is a "true" recursion or a "false" one.

> Strictly speaking, this problem is not recursive in nature.

Strictly speaking, problems do not have nature. Everything solvable "procedurally" has a purely recursive solution (a Turing machine is computationally equivalent to a Church's lambda calculus to a Markov's recursion etc etc)

To illustrate a point, here is a purely recursive solution of a subproblem: find if an array contains a given number (it is intentionally written in haskel; I don't want to do somebody's homework):

if_has_value :: Int -> [Int] -> Bool
if_has_value v [] = False
if_has_value v (x:xs) | v == x = True
                      | _      = if_has_value v xs

[uskok]

>> uskok, what you're doing is just traversing with the help of recursion.
I am aware of it. It was meant to be a suggestion to the original poster, not a complete solution.

Basically, one function traverses the array, and for each element calls another function that traverses the rest of the array, searching for sum - element . Similar to a solution that would use two nested loops.

Neither local nor global variables are needed to solve the problem. Everything can be sent by arguments.
On the other hand, maybe I'm missing something and violating the ideal of functional programming in another way. :)