Learning Targets:

  • Determine the result of executing recursive method.

Essential Knowledge:

  • Recursion is a method that calls itself.
  • Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.
    • To accomplish this is a recursive method contains a conditional.
  • each recursive call has its own set of local variables, including formal parameters.
  • parameter values capture the progress of a recursive process, much like a loop control variable vales capture the progress of a loop.
  • any recursive sloution can be replicated throu the user of an i word (iteration, index, or integer) approach.
    • exclusion statement: writing recursive program code is outside the scope of the AP CSA course and exam but it is allowed. but sometimes it is more straightforward than iterative.

      Example of recursion:

      public static void main(String[] args) {
  System.out.println("Hello World!");
  main(args);
}

      Example of recursion with a base case:

      public static void main(String[] args) {
  System.out.println("Hello World!");
  if (args.length > 0) {
 main(args);
  }
}

      Example of recursion with a base case and a recursive call including formal parameters:

      public static void main(String[] args) {
  System.out.println("Hello World!");
  if (args.length > 0) {
 main(args);
  }
}

This is a recursive code, do we all agree with that?

note : pay attention

// void recursive method
public static void simpleRecur(int n)
{
    system.out.println(n);
    if (n > 2) // the if statement cuases the recursion to end when n <. 2 since the recursive call 
    // since the recursive call only occurs when n > 2 
        simpleRecur(n-1); 
    system.out.println(n);

}

lets trace the call simpleRecur(4) | Call Stack | Variable trace for call | |—|—| | simpleRecur(4) | n=4 4>2, T | | simpleRecur(3) | n=3 2>2, T | | simpleRecur(2) | n=2 2>2, F |

pop corn hack!!!!!!

Note: 0.01 extra credit for each correct answer, we have limit Paraas to 3 answers.

What would be the output of the code above? (0.01 extra credit)

here is a modified code from above, what would be the output of the code above? and what would be the base case? (0.01 extra credit)

// infinite 
public static void simpleRecur(int n)
{
    system.out.println(n);
    if (n > 2)
        simpleRecur(n+3); 
    system.out.println(n);

}
Call Stack Variable trace for call
simpleRecur(4) n=4 4>2, T
simpleRecur(7) n=7 7>2, T
simpleRecur(10) n=10 10>2, T

n is getting larger infinitely. java will eventually run out of memory and cause a CallStackOverflowException.

// non-void recursive method
public static void simpleRecur(int n)
{
    system.out.println(n);
    if (n == 0)
        return 0;
    return n + system.out.println(n);

}
Call Stack Variable trace for call
simpleRecur(8)=8 + simpleRecur(4) n=8 8==0 F
simpleRecur(4)=4 + simpleRecur(2) n=4 4==0 F
simpleRecur(2)=2 + simpleRecur(1) n=2 2==0 F
simpleRecur(1)=1 + simpleRecur(0) n=1 1==0 F
simpleRecur(0)=0 n= 0==0 T

but where does it return 0 to?

Enter the password to answer:

what would be the return of simpleRecur(8)?

Enter the password answer:

most of this might have flew over your head, but don’t fret.

real world examples of recursion:

Russian dolls

  • Russian dolls are a set of wooden dolls of decreasing size placed one inside another.
  • The dolls are made in such a way that each doll can be opened in half to reveal a smaller doll inside.
  • Lets set the smallest as the base case
  • The dolls are a recursive structure because each doll is a smaller version of the previous doll.

Russian dolls

mr. finn here is gonna talk about how to visualize recursion better.