How to understand the principles of recursions in practice?

I started learning recursions and it seemed like I understood how they work. But as soon as I tried to pass a quiz, I found that I actually didn’t. Here is some code from latest task I tried to pass. Here I tried to find a factorial. To do this I have to multiply all the numbers from 1 till the N number.

Here is some code:

public class App {
public static void main(String[] args) {
    f(1);
}

private static void f(int n) {
    System.out.print(n);
    if (n < 7) {
        f(2 * n);
    }
}
}

I tried to multiply these nums and to multiply the product for 2. But I failed when saw that the result isn’t 5040. The actual output is 1248. Maybe I was doing actions in wrong order?

2
Leave a Reply

avatar
2 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Jason Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
Jason
Guest

Let’s take a look how to multiply numbers from 1 to n using recurrency:

public static void main(String[] args) {
    long result = mulFromOneTo(30);
}

private long mulFromOneTo(int number) {
   if (number == 1) {
       return 1;
   } else {
       return number * mulFromOneTo(number - 1);
   }
}

I don’t want to give you completely prepared source code – but I hope it’ll help you a bit.

Jason
Guest

Andrezej’s answer is a good top-down approach. Let’s have a look at why your code doesn’t work: If we summarize what f is doing, it prints n and it will call itself recursively with 2 * n when n is less than 7. So in your example, you first call f(1) so it prints 1 and calls f(2), which prints 2 and calls f(4), prints 4, calls f(8), prints 8 and stop. So your function is not printing the number 1248, but it’s printing 1, 2, 4 and 8 independently. The total computation done by your recursive function is (2… Read more »