Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Can any function that calls itself be considered recursive?

pseudocode recursive

  • Please log in to reply
8 replies to this topic

#1 Bob93

Bob93

    CC Lurker

  • Just Joined
  • Pip
  • 3 posts

Posted 30 August 2010 - 02:31 PM

For instance this: (pseudocode)
function pickFromList returns int
{
output: Pick a number from 1 to 10
get input

if number is from 1 to 10
{
return number
}

else
{
output: Your number is not from 1 to 10
return pickFromList
}

}

  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 30 August 2010 - 05:05 PM

It can be, but I would consider that function a great example of when NOT to use it.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 Bob93

Bob93

    CC Lurker

  • Just Joined
  • Pip
  • 3 posts

Posted 30 August 2010 - 09:37 PM

Why is it a bad idea to use it like this?
Should I use a while loop instead?
Thanks.
  • 0

#4 josep

josep

    CC Resident

  • Just Joined
  • PipPipPipPip
  • 55 posts

Posted 31 August 2010 - 01:38 AM

Normally, a recursive function should have a control variable to avoid an infinite loop. In your case, i think you should specify the size of the list and the logic in which you are picking your numbers.
becuase the way it is, it is very possible to run into an infinite loop.

Good Luck!
  • 0

#5 Momerath

Momerath

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 282 posts
  • Programming Language:C, Java, C++, C#, PHP, (Visual) Basic, Python, JavaScript, Perl, Visual Basic .NET, Pascal, Ada, Assembly, Fortran, Scheme
  • Learning:Others

Posted 31 August 2010 - 04:25 AM

It's a bad idea because when you call the method, the system has to add more information to the stack (yes, I see you Functional languages with your tail recursive optimization, but this is true most of the time!) and eventually you'll run out of stack space and your program will crash. A while loop is a much better choice.
  • 0

#6 Bob93

Bob93

    CC Lurker

  • Just Joined
  • Pip
  • 3 posts

Posted 31 August 2010 - 09:28 PM

Thanks for the replies
Would using a while(true) loop be a good idea?

function pickFromList returns int
{
 while (true)
 {
   output: Pick a number from 1 to 10
   get input

   if number is from 1 to 10
   {
   return number
   }

   else
   {
   output: Your number is not from 1 to 10
   }
 }
}

  • 0

#7 Momerath

Momerath

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 282 posts
  • Programming Language:C, Java, C++, C#, PHP, (Visual) Basic, Python, JavaScript, Perl, Visual Basic .NET, Pascal, Ada, Assembly, Fortran, Scheme
  • Learning:Others

Posted 31 August 2010 - 10:26 PM

Yes, using a while loop would be a good idea :)
  • 0

#8 zoranh

zoranh

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 187 posts

Posted 01 September 2010 - 12:54 AM

Why is it a bad idea to use it like this?
Should I use a while loop instead?
Thanks.

Your code is an example of Tail Recursion, which occurs when recursive call is the last statement in the function. In that case code can be formally transformed into iterative form without loss of functionality. Even some optimizers do that for you when they encounter the tail recursion.

Recursive call is much more expensive than iteration because complete stack frame must be built, containing all arguments to the method, some register values, local variables, return address... This is not a small structure anyway, and that's why recursive call is slow compared to iteration.
  • 0

#9 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 01 September 2010 - 04:28 AM

Thanks for the replies
Would using a while(true) loop be a good idea?

function pickFromList returns int
{
 while (true)
 {
   output: Pick a number from 1 to 10
   get input

   if number is from 1 to 10
   {
   return number
   }

   else
   {
   output: Your number is not from 1 to 10
   }
 }
}

while (true) is an infinite loop. You want while (number is not from 1 to 10).
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Also tagged with one or more of these keywords: pseudocode, recursive

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download