CODEWITHSUNDEEP
recursionjava
Ivan
Ivan

Reputation:

Recursion in java help

I am new to the site and am not familiar with how and where to post so please excuse me. I am currently studying recursion and am having trouble understanding the output of this program. Below is the method body.

public static int Asterisk(int n)
{
if (n<1)
return;

Asterisk(n-1);

  for (int i = 0; i<n; i++)
  {
      System.out.print("*");
  }
  System.out.println();
}

This is the output

 *
 **
 ***
 ****
 *****

it is due to the fact that the "Asterisk(n-1)" lies before the for loop.

I would think that the output should be 

****
***
**
*

Upvotes: 0

Views: 57

Answers (3)

clicky
clicky

Reputation: 865

Think of recursive calls in terms of a stack. A stack is a data structure which adds to the top of a pile. A real world analogy is a pile of dishes where the newest dish goes on the top. Therefore recursive calls add another layer to the top of the stack, then once some criteria is met which prevents further recursive calls, the stack starts to unwind and we work our way back down to the original item (the first plate in pile of dishes).

The input of a recursive method tends towards a base case which is the termination factor and prevents the method from calling itself indefinitely (infinite loop). Once this base condition is met the method returns a value rather than calling itself again. This is how the stack in unwound.

In your method, the base case is when $n<1$ and the recursive calls use the input $n-1$. This means the method will call itself, each time decreasing $n$ by 1, until $n<1$ i.e. $n=0$. Once the base condition is met, the value 0 is returned and we start to execute the $for$ loop. This is why the first line contains a single asterix.

So if you run the method with an input of 5, the recursive calls build a stack of values of $n$ as so

0
1
2
3
4
5

Then this stack is unwound starting with the top, 0, all the way down to 5.

Upvotes: 0

Jose Fonseca
Jose Fonseca

Reputation: 416

There are two ways to create programming loops. One is using imperative loops normally native to the language (for, while, etc) and the other is using functions (functional loops). In your example the two kinds of loops are presented.

One loop is the unrolling of the function 

Asterisk(int n)

This unrolling uses recursion, where the function calls itself. Every functional loop must know when to stop, otherwise it goes on forever and blows up the stack. This is called the "stopping condition". In your case it is :

if (n<1)
return;

There is bidirectional equivalence between functional loops and imperative loops (for, while, etc). You can turn any functional loop into a regular loop and vice versa.

IMO this particular exercise was meant to show you the two different ways to build loops. The outer loop is functional (you could substitute it for a for loop) and the inner loop is imperative.

Upvotes: 0

Somenath Sinha
Somenath Sinha

Reputation: 1214

This is the way head recursion works. The call to the function is made before execution of other statements. So, Asterisk(5) calls Asterisk(4) before doing anything else. This further cascades into serial function calls from Asterisk(3) → Asterisk(2) → Asterisk(1) → Asterisk(0).

Now, Asterisk(0) simply returns as it passes the condition n<1. The control goes back to Asterisk(1) which now executes the rest of its code by printing n=1 stars. Then it relinquishes control to Asterisk(2) which again prints n=2 stars, and so on. Finally, Asterisk(5) prints its n=5 stars and the function calls end. This is why you see the pattern of ascending number of stars.

Upvotes: 2

Related Questions