Recursive Function

Discussion in 'C++' started by cplusplusquestion@gmail.com, Jun 25, 2008.

  1. Guest

    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[j] != -1) {
    /*... using a[j] to calculate some value...*/
    a[j]=-1;
    fun(a);
    }
    }

    to:

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

    and make sure the result will be same.
    , Jun 25, 2008
    #1
    1. Advertising

  2. Daniel Pitts Guest

    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[j] != -1) {
    > /*... using a[j] to calculate some value...*/
    > a[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[j] != -1) {
    calculateSomeValue(a[j]);
    a[j]=-1;
    fun(a);
    }
    }
    }
    }

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

    Now, if you need to pass more information into calculateSomeValue to
    make it work, let us know what and why.

    --
    Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
    Daniel Pitts, Jun 25, 2008
    #2
    1. Advertising

  3. Greg Herlihy Guest

    On Jun 24, 9:47 pm, Daniel Pitts
    <> wrote:
    > 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[j] != -1) {
    > >                    /*... using a[j] to calculate some value...*/
    > >                    a[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[j] != -1) {
    >          calculateSomeValue(a[j]);
    >          a[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[j] != -1)
    {
    calculateSomeValue(a[j]);
    a[j] = -1;
    fun(a);
    }
    }

    Greg
    Greg Herlihy, Jun 25, 2008
    #3
  4. Daniel Pitts Guest

    Greg Herlihy wrote:
    > On Jun 24, 9:47 pm, Daniel Pitts
    > <> wrote:
    >> 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[j] != -1) {
    >>> /*... using a[j] to calculate some value...*/
    >>> a[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[j] != -1) {
    >> calculateSomeValue(a[j]);
    >> a[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[j] != -1)
    > {
    > calculateSomeValue(a[j]);
    > a[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[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/>
    Daniel Pitts, Jun 25, 2008
    #4
  5. Guest

    >
    > 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[j] != -1)
    >                 {
    >                     calculateSomeValue(a[j]);
    >                     a[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[j] != -1)
    {
    // calculateSomeValue(a[j]);
    cout << i << " " << j << " " << a.n[j] << endl;
    a.n[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[j] = i+j;
    }

    fun(b);
    }
    ******************************************************************************
    , Jun 26, 2008
    #5
  6. Daniel Pitts Guest

    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[j] != -1)
    >> {
    >> calculateSomeValue(a[j]);
    >> a[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[j] != -1)
    > {
    > // calculateSomeValue(a[j]);
    > cout << i << " " << j << " " << a.n[j] << endl;
    > a.n[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[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/>
    Daniel Pitts, Jun 26, 2008
    #6
  7. Guest

    On Jun 27, 6:15 am, Daniel Pitts
    <> wrote:
    > 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[j] != -1)
    > >>                 {
    > >>                     calculateSomeValue(a[j]);
    > >>                     a[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[j] != -1)
    > >            {
    > > //                 calculateSomeValue(a[j]);
    > >                    cout << i << " " << j << " " << a.n[j] << endl;
    > >                    a.n[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[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.
    , Jun 27, 2008
    #7
  8. Daniel Pitts Guest

    wrote:
    > On Jun 27, 6:15 am, Daniel Pitts
    > <> wrote:
    >> 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[j] != -1)
    >>>> {
    >>>> calculateSomeValue(a[j]);
    >>>> a[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[j] != -1)
    >>> {
    >>> // calculateSomeValue(a[j]);
    >>> cout << i << " " << j << " " << a.n[j] << endl;
    >>> a.n[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[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/>
    Daniel Pitts, Jun 27, 2008
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tyron

    Recursive function

    Tyron, Apr 16, 2004, in forum: VHDL
    Replies:
    1
    Views:
    617
    valentin tihomirov
    Apr 16, 2004
  2. n00m
    Replies:
    12
    Views:
    1,099
  3. vamsi
    Replies:
    21
    Views:
    2,043
    Keith Thompson
    Mar 9, 2009
  4. Mark Piffer
    Replies:
    9
    Views:
    895
    luserXtrog
    May 15, 2009
  5. Alok
    Replies:
    3
    Views:
    237
Loading...

Share This Page