Velocity Reviews > C++ > Recursive Function

# Recursive Function

cplusplusquestion@gmail.com
Guest
Posts: n/a

 06-25-2008
As discussion last time, I am thinking if it is possible to change the
recursive function from:

void fun(Array a){
for (int i=0; i<MAX1; i++)
for(int j=0; j<MAX2; j++){
if ( a[i][j] != -1) {
/*... using a[i][j] to calculate some value...*/
a[i][j]=-1;
fun(a);
}
}

to:

void fun(Array& a){
/*......*/
}

and make sure the result will be same.

Daniel Pitts
Guest
Posts: n/a

 06-25-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> As discussion last time, I am thinking if it is possible to change the
> recursive function from:
>
> void fun(Array a){
> for (int i=0; i<MAX1; i++)
> for(int j=0; j<MAX2; j++){
> if ( a[i][j] != -1) {
> /*... using a[i][j] to calculate some value...*/
> a[i][j]=-1;
> fun(a);
> }
> }
>
> to:
>
> void fun(Array& a){
> /*......*/
> }
>
> and make sure the result will be same.

Its depends.
If you could re-write it as:

void fun(Array a) {
for (int i=0; i<MAX1; i++) {
for (int j=0; j<MAX2; j++) {
if ( a[i][j] != -1) {
calculateSomeValue(a[i][j]);
a[i][j]=-1;
fun(a);
}
}
}
}

Then it would be trivial. Just remove the "fun(a)" call, since it isn't
actually doing anything productive.

make it work, let us know what and why.

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

Greg Herlihy
Guest
Posts: n/a

 06-25-2008
On Jun 24, 9:47*pm, Daniel Pitts
<(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> > As discussion last time, I am thinking if it is possible to change the
> > recursive function from:

>
> > void fun(Array a){
> > * * for (int i=0; i<MAX1; i++)
> > * * * * for(int j=0; j<MAX2; j++){
> > * * * * * * * *if ( a[i][j] != -1) {
> > * * * * * * * * * */*... using a[i][j] to calculate some value...*/
> > * * * * * * * * * *a[i][j]=-1;
> > * * * * * * * * * *fun(a);
> > * * * *}
> > }

>
> > to:

>
> > void fun(Array& a){
> > * */*......*/
> > }

>
> > and make sure the result will be same.

>
> Its depends.
> If you could re-write it as:
>
> * void fun(Array a) {
> * * for (int i=0; i<MAX1; i++) {
> * * *for (int j=0; j<MAX2; j++) {
> * * * *if ( a[i][j] != -1) {
> * * * * *calculateSomeValue(a[i][j]);
> * * * * *a[i][j]=-1;
> * * * * *fun(a);
> * * * *}
> * * *}
> * * }
> * }
>
> Then it would be trivial. Just remove the "fun(a)" call, since it isn't
> actually doing anything productive.

How do you figure? Without knowing how "Array" is defined, it is not
possible for us to tell whether the call to fun(a) serves any useful
purpose or not. For example, one could imagine a more complete program
fragment - and one for which it is clear that the call to fun(a) is
useful:

const int MAX1 = 16;
const int MAX2 = 32;

typedef int (&Array)[MAX1][MAX2];

void fun(Array a)
{
for (int i = 0; i < MAX1; i++)
for (int j = 0; j < MAX2; j++)
if (a[i][j] != -1)
{
calculateSomeValue(a[i][j]);
a[i][j] = -1;
fun(a);
}
}

Greg

Daniel Pitts
Guest
Posts: n/a

 06-25-2008
Greg Herlihy wrote:
> On Jun 24, 9:47 pm, Daniel Pitts
> <(E-Mail Removed)> wrote:
>> (E-Mail Removed) wrote:
>>> As discussion last time, I am thinking if it is possible to change the
>>> recursive function from:
>>> void fun(Array a){
>>> for (int i=0; i<MAX1; i++)
>>> for(int j=0; j<MAX2; j++){
>>> if ( a[i][j] != -1) {
>>> /*... using a[i][j] to calculate some value...*/
>>> a[i][j]=-1;
>>> fun(a);
>>> }
>>> }
>>> to:
>>> void fun(Array& a){
>>> /*......*/
>>> }
>>> and make sure the result will be same.

>> Its depends.
>> If you could re-write it as:
>>
>> void fun(Array a) {
>> for (int i=0; i<MAX1; i++) {
>> for (int j=0; j<MAX2; j++) {
>> if ( a[i][j] != -1) {
>> calculateSomeValue(a[i][j]);
>> a[i][j]=-1;
>> fun(a);
>> }
>> }
>> }
>> }
>>
>> Then it would be trivial. Just remove the "fun(a)" call, since it isn't
>> actually doing anything productive.

>
> How do you figure? Without knowing how "Array" is defined, it is not
> possible for us to tell whether the call to fun(a) serves any useful
> purpose or not. For example, one could imagine a more complete program
> fragment - and one for which it is clear that the call to fun(a) is
> useful:
>
> const int MAX1 = 16;
> const int MAX2 = 32;
>
> typedef int (&Array)[MAX1][MAX2];
>
> void fun(Array a)
> {
> for (int i = 0; i < MAX1; i++)
> for (int j = 0; j < MAX2; j++)
> if (a[i][j] != -1)
> {
> calculateSomeValue(a[i][j]);
> a[i][j] = -1;
> fun(a);
> }
> }
>
> Greg
>
>

Lets walk through the program shall we...
first, calculateSomeValue(a[0][0]) gets called.
a[0][0] = -1;
call to fun(a)

a[0][0] == -1, so it skips
calculateSomeValue(a[0][1]) gets caled
a[0][1] = -1;
call to fun(a)
a[0][0] and a[0][1] get skipped.... See where I'm going? If you don't
call fun(a), the same calculations will get done, minus the overactive
recursion and extra comparisons to -1

So, the call to fun(a) is still not useful. If you replace
calculateSomeValue with std::cout << i << ", " << j << ": " << a[i][j]
<< std::endl; You will see that the output is the same with or without
fun(a), but significantly more efficient without it.

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

cplusplusquestion@gmail.com
Guest
Posts: n/a

 06-26-2008
>
> How do you figure? Without knowing how "Array" is defined, it is not
> possible for us to tell whether the call to fun(a) serves any useful
> purpose or not. For example, one could imagine a more complete program
> fragment - and one for which it is clear that the call to fun(a) is
> useful:
>
> * * const int MAX1 = 16;
> * * const int MAX2 = 32;
>
> * * typedef int (&Array)[MAX1][MAX2];
>
> * * void fun(Array a)
> * * {
> * * * * for (int i = 0; i < MAX1; i++)
> * * * * * * for (int j = 0; j < MAX2; j++)
> * * * * * * * * if (a[i][j] != -1)
> * * * * * * * * {
> * * * * * * * * * * calculateSomeValue(a[i][j]);
> * * * * * * * * * * a[i][j] = -1;
> * * * * * * * * * * fun(a);
> * * * * * * * * }
> * * }
>
> Greg

Here is my example code:

************************************************** ******************************
#include <iostream>

using namespace std;

struct Array{
int n[3][3];
};

void fun(Array a)
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (a.n[i][j] != -1)
{
// calculateSomeValue(a[i][j]);
cout << i << " " << j << " " << a.n[i][j] << endl;
a.n[i][j] = -1;
fun(a); //with it and without it will be different
}
}

int main(){
Array b;

for(int i=0; i<3; i++)
for(int j=0; j<3; j++){
b.n[i][j] = i+j;
}

fun(b);
}
************************************************** ****************************

Daniel Pitts
Guest
Posts: n/a

 06-26-2008
(E-Mail Removed) wrote:
>> How do you figure? Without knowing how "Array" is defined, it is not
>> possible for us to tell whether the call to fun(a) serves any useful
>> purpose or not. For example, one could imagine a more complete program
>> fragment - and one for which it is clear that the call to fun(a) is
>> useful:
>>
>> const int MAX1 = 16;
>> const int MAX2 = 32;
>>
>> typedef int (&Array)[MAX1][MAX2];
>>
>> void fun(Array a)
>> {
>> for (int i = 0; i < MAX1; i++)
>> for (int j = 0; j < MAX2; j++)
>> if (a[i][j] != -1)
>> {
>> calculateSomeValue(a[i][j]);
>> a[i][j] = -1;
>> fun(a);
>> }
>> }
>>
>> Greg

>
> Here is my example code:
>
> ************************************************** ******************************
> #include <iostream>
>
> using namespace std;
>
> struct Array{
> int n[3][3];
> };
>
> void fun(Array a)
> {
> for (int i = 0; i < 3; i++)
> for (int j = 0; j < 3; j++)
> if (a.n[i][j] != -1)
> {
> // calculateSomeValue(a[i][j]);
> cout << i << " " << j << " " << a.n[i][j] << endl;
> a.n[i][j] = -1;
> fun(a); //with it and without it will be different
> }
> }
>
> int main(){
> Array b;
>
> for(int i=0; i<3; i++)
> for(int j=0; j<3; j++){
> b.n[i][j] = i+j;
> }
>
> fun(b);
> }
> ************************************************** ****************************

ah HAH!
I was assuming that Array had object semantics, not value semantics...

Now, if you change
void fun(Array a)
to
void fun(Array &a)

You will see that calling fun(a) makes no difference.

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

cplusplusquestion@gmail.com
Guest
Posts: n/a

 06-26-2008
On Jun 27, 6:15*am, Daniel Pitts
<(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> >> How do you figure? Without knowing how "Array" is defined, it is not
> >> possible for us to tell whether the call to fun(a) serves any useful
> >> purpose or not. For example, one could imagine a more complete program
> >> fragment - and one for which it is clear that the call to fun(a) is
> >> useful:

>
> >> * * const int MAX1 = 16;
> >> * * const int MAX2 = 32;

>
> >> * * typedef int (&Array)[MAX1][MAX2];

>
> >> * * void fun(Array a)
> >> * * {
> >> * * * * for (int i = 0; i < MAX1; i++)
> >> * * * * * * for (int j = 0; j < MAX2; j++)
> >> * * * * * * * * if (a[i][j] != -1)
> >> * * * * * * * * {
> >> * * * * * * * * * * calculateSomeValue(a[i][j]);
> >> * * * * * * * * * * a[i][j] = -1;
> >> * * * * * * * * * * fun(a);
> >> * * * * * * * * }
> >> * * }

>
> >> Greg

>
> > Here is my example code:

>
> > ************************************************** ******************************
> > #include <iostream>

>
> > using namespace std;

>
> > struct Array{
> > * *int n[3][3];
> > };

>
> > void fun(Array a)
> > {
> > * *for (int i = 0; i < 3; i++)
> > * *for (int j = 0; j < 3; j++)
> > * * * * * *if (a.n[i][j] != -1)
> > * * * * * *{
> > // * * * * * * * * calculateSomeValue(a[i][j]);
> > * * * * * * * * * *cout << i << " " << j << " " << a.n[i][j] << endl;
> > * * * * * * * * * *a.n[i][j] = -1;
> > * * * * * * * * * *fun(a); * //with it and without it will be different
> > * * * * * *}
> > }

>
> > int main(){
> > * *Array b;

>
> > * *for(int i=0; i<3; i++)
> > * * * * * *for(int j=0; j<3; j++){
> > * * * * * * * * * *b.n[i][j] = i+j;
> > * * * * * *}

>
> > * *fun(b);
> > }
> > ************************************************** ****************************

>
> ah HAH!
> I was assuming that Array had object semantics, not value semantics...
>
> Now, if you change
> void fun(Array a)
> to
> void fun(Array &a)
>
> You will see that calling fun(a) makes no difference.
>
> --
> Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

passing with value and passing with reference, the result is different.

Daniel Pitts
Guest
Posts: n/a

 06-27-2008
(E-Mail Removed) wrote:
> On Jun 27, 6:15 am, Daniel Pitts
> <(E-Mail Removed)> wrote:
>> (E-Mail Removed) wrote:
>>>> How do you figure? Without knowing how "Array" is defined, it is not
>>>> possible for us to tell whether the call to fun(a) serves any useful
>>>> purpose or not. For example, one could imagine a more complete program
>>>> fragment - and one for which it is clear that the call to fun(a) is
>>>> useful:
>>>> const int MAX1 = 16;
>>>> const int MAX2 = 32;
>>>> typedef int (&Array)[MAX1][MAX2];
>>>> void fun(Array a)
>>>> {
>>>> for (int i = 0; i < MAX1; i++)
>>>> for (int j = 0; j < MAX2; j++)
>>>> if (a[i][j] != -1)
>>>> {
>>>> calculateSomeValue(a[i][j]);
>>>> a[i][j] = -1;
>>>> fun(a);
>>>> }
>>>> }
>>>> Greg
>>> Here is my example code:
>>> ************************************************** ******************************
>>> #include <iostream>
>>> using namespace std;
>>> struct Array{
>>> int n[3][3];
>>> };
>>> void fun(Array a)
>>> {
>>> for (int i = 0; i < 3; i++)
>>> for (int j = 0; j < 3; j++)
>>> if (a.n[i][j] != -1)
>>> {
>>> // calculateSomeValue(a[i][j]);
>>> cout << i << " " << j << " " << a.n[i][j] << endl;
>>> a.n[i][j] = -1;
>>> fun(a); //with it and without it will be different
>>> }
>>> }
>>> int main(){
>>> Array b;
>>> for(int i=0; i<3; i++)
>>> for(int j=0; j<3; j++){
>>> b.n[i][j] = i+j;
>>> }
>>> fun(b);
>>> }
>>> ************************************************** ****************************

>> ah HAH!
>> I was assuming that Array had object semantics, not value semantics...
>>
>> Now, if you change
>> void fun(Array a)
>> to
>> void fun(Array &a)
>>
>> You will see that calling fun(a) makes no difference.
>>
>> --
>> Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

>
> passing with value and passing with reference, the result is different.

Yes, but is the "passing with reference" result "wrong"?

If it isn't, then you can pass by reference and then remove the recursion.

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Mark Piffer C Programming 9 05-15-2009 07:54 AM vamsi C Programming 21 03-09-2009 10:53 PM n00m C++ 12 03-13-2008 03:18 PM Alok Ruby 3 04-13-2006 11:53 AM komal C++ 6 01-25-2005 11:13 AM