This week's book giveaway is in the Java in General forum.
We're giving away four copies of Think Java: How to Think Like a Computer Scientist and have Allen B. Downey & Chris Mayfield on-line!
See this thread for details.
Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

recursive

 
abalfazl hossein
Ranch Hand
Posts: 635
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
http://cse.unl.edu/~dsadofs/RecursionTutorial/index.php?s=algorithms#recfactalg



Well, as stated in the description of a recursive definition, a base case and inductive rule were needed. In this case, fact(0)=1 is the base case. This is a logical place to start, seeing as how the n in fact(n) must be larger than or equal to 1 (only positive integers). The other half is the inductive rule of the problem, which in this case is represented by “fact(n)=fact(n-1)*n”. We can see the logic in this, as the factorial of any number, is simply the factorial of the number one smaller than it, times the number you’re finding the factorial of.


In this tutorial , it is said that a recursive function divide to the two part, Base and inductive


Now, look at this function:




In this function, If n>0 is base, and rem=n%10;
s += rem;
sum(n/10)

Is inductive?

Is it right that said every recursive function divide to the two parts?

 
Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15272
37
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What language is that second function in? It's not Java, it's not C, it looks like some kind of pseudo-code, and it doesn't look complete. What happens in the second function when n == 0 or n < 0? That (the missing part) would be the base case. The inductive case is what's between the { and } of the if-statement; that's the part that does the recursive call.

Recursive functions always need an if-statement in some form. If there is no terminating condition (the base case), you would have an infinite recursive loop, and the program would end with a stack overflow error.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic