CODEWITHSUNDEEP
javarecursion
user3195991
user3195991

Reputation: 79

Can't understand how recursion works in this example

I was given the following code:

public int func(int n){
  if(n == 1)
     return 2;
  else 
     return 3 * func(n-1)+1;
}

I can understand recursion in things like factorial and fibonacci, but for this one I cant. I tried to trace the logic:

if n is 3:
return 3 * func(2) + 1
return 3 * func(1) + 1
return 3 * 2 + 1
return 7

I always end up with 7 with any other number and I know this is wrong because I get different values when I run the program. Can you help me understand how recursion works here?

Upvotes: 3

Views: 168

Answers (7)

Babak
Babak

Reputation: 26

As a general rule a recursive method has two parts,

  1. The part for solving primitive problem, here in your example is if(n == 1) return 2;

  2. The part for dividing the problem into smaller problems so that finally it falls under part 1 (primitive problem) else return 3 * func(n-1)+1;

This is the very nature of Divide and Conquer algorithms that tend to divide the problem into smaller pieces in each round until they became solvable. Then by joining the solved pieces, the original problem gets solved.

Upvotes: 0

Алексей
Алексей

Reputation: 1847

when n=3 you get

func(3) = > return 3 * func(2) + 1

where func(2) is 

func(2) = > return 3 * func(1) + 1

where func(1) is 

func(1) = > return 2

once you combine them you get that

func(3) => return 3 * (3 * (2) + 1) + 1

func(3) => return 22

Upvotes: 1

Simeon Visser
Simeon Visser

Reputation: 122516

  • If n is 1 it returns 2 (so func(1) = 2).
  • If n is 2 it returns 3 * func(1) + 1, which is 3 * 2 + 1 = 7 (so func(2) = 7).
  • If n is 3 it returns 3 * func(2) + 1, which is 3 * 7 + 1 = 22 (so func(3) = 22).
  • If n is 4 it returns 3 * func(3) + 1, which is 3 * 22 + 1 = 67 (so func(4) = 67).
  • ...

And so on. In other words, when n = 1 it simply returns 2 and it all other cases it returns the value for func(n - 1) times three and with one added.

Upvotes: 2

MoRe
MoRe

Reputation: 1538

You have to reinput that value you get for the deepest recursion call into the previous level and so forth.

func(1) = 2
func(2) = 3 * func(1) + 1 = 7
func(3) = 3 * func(2) + 1 = 22
func(4) = 3 * func(3) + 1 = 67

Upvotes: 0

Choppin Broccoli
Choppin Broccoli

Reputation: 3076

You're close, but missing a key point:

func(3) is: 3 * func(2) + 1
func(2) is: 3 * func(1) + 1
func(1) is: 2

Therefore, func(2) is 3*2+1 = 7.
And func(3) is 3*7+1 = 22

Upvotes: 1

lindenrovio
lindenrovio

Reputation: 357

if n is 3

func(3)
=3*func(2)+1
=3*(3*func(1)+1)+1
=3*(3*2+1)+1
=22

if n is 4

func(4)
=3*func(3)+1
=3*22+1
=67

Upvotes: 1

user2336315
user2336315

Reputation: 16067

I think this is self-explanatory, if you need more informations just comment !

if n is 3:
return 3 * func(2) + 1
return 3 * (3 * func(1) + 1) + 1 //func(2) is equals to 3 * func(1) + 1
return 3 * (3 * 2 + 1) + 1 //func(1) is equals to 2
return 22

Upvotes: 4

Related Questions