Scribd
Upload
42 views6 pages

Notes 3.1 - Recursion

The document provides an introduction to recursion in computer science, explaining that recursion occurs when a method calls itself to solve similar subproblems. It discusses the use of a stack data structure to manage method calls and illustrates this with examples, including calculating powers and other recursive functions. The document emphasizes the elegance of recursive solutions compared to iterative ones and notes the importance of understanding recursion for AP Computer Science exams.

Uploaded by

ihhihihhi7
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
42 views6 pages

Notes 3.1 - Recursion

The document provides an introduction to recursion in computer science, explaining that recursion occurs when a method calls itself to solve similar subproblems. It discusses the use of a stack data structure to manage method calls and illustrates this with examples, including calculating powers and other recursive functions. The document emphasizes the elegance of recursive solutions compared to iterative ones and notes the importance of understanding recursion for AP Computer Science exams.

Uploaded by

ihhihihhi7
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

November 04, 2016

Intro to Recursion
AP Computer Science

Have you ever Googled recursion?

What is Recursion?
When a method calls itself (usually to solve a similar, simpler problem)

Example: public int mist(int n){


if(n==1)
return 3;
else
return 3*mist(n-1);
}

Why are you learning it?


Problems that can be solved by dividing the bigger problem into
subproblems that are similar in nature are often coded more
elegantly recursively than iteratively.

Though we will see many "trivial" examples to start, we will


eventually learn some common recursive algorithms.

P.S. Collegeboard loves to quiz you on tracing recursive code...


November 04, 2016

How does it work?


Makes use of a data structure called a stack.

Last In, First Out (LIFO)

Actions: push (add element to top)


pop (remove element from the top)

How does that relate to recursion?


Each method call is pushed onto the current stack. Numerous
calls will be pushed onto the stack until the base case is reached.

The stack is then popped one element at a time, returning


values/doing some task, until the original call is evaluated.

Example:
public int power(int base, int exp){
if(exp == 0)
return 1;
else
return base * power(base, exp-1);
}

power(2, 4)
November 04, 2016

Example:
public int power(int base, int exp){
if(exp == 0)
return 1;
else
return base * power(base, exp-1);
}
power(2, 4)

Example:
public int power(int base, int exp){
if(exp == 0)
return 1;
else
return base * power(base, exp-1);
}
power(2, 4)
November 04, 2016

Example:

int result = identity(10);


System.out.println("The final answer is " + result);

public int identity(int num){


if(num < 1){
return 10;
}else{
return num + identity(num - 2);
}
}

Example:

int result2 = negative(-3);


System.out.println("The final answer is " + result2);

public int negative(int num){


if(num >= 20){
return -5;
}else{
return negative(num + 4) + 2 * num;
}
}
November 04, 2016

Example:

int result3 = product(1);


System.out.println("The final answer is " + result3);

public int product(int num){


if(num > 20){
return -1;
}else{
return num * product(-2 * num);
}
}

Example:

void weirdo(int x){


if( x > 1 ){
weirdo(x/2);
}
System.out.print(x + “ “);
}

What is the output of the call weirdo(40)?


November 04, 2016

Example:

void weirdom(int x){


System.out.print(x + “ “);
if( x > 1 ){
weirdom(x/2);
}
}

What is the output of the call weirdom(40)?

You might also like