Not Yet Answered # search a sum of 2 numbers in an array with recurtion

gerard4143 371 xavier666 56 uskok xavier666 56 nezachem 616 uskok Hey, so I wanna ask how I need to create a method who will remove word if in that word is 2 same chars. Example: "Potato" in this word there is a 2 "o" chars so this word will need to be removed. "Forum" in this word there is no ...

0

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.

0

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

0

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.

0

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.

0

> **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
```

0

**>> 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. :)

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Help! I want to create a java program that finds the highest even integer among the values entered by the user. Stop asking values when a value less than 1 have been entered. If no even integer is entered, display "No Even Integer"

Here is the sample output that I ...

I am writing a java program that needs to execute shell commands, so I wrote a function that would take the command to execute as a string (ie: "mkdir ~/Folder1") and execute that command with the shell. Here is the function:

```
try
{
Runtime run = Runtime.getRuntime();
Process pr = ...
```