CSE 8B Chapter 18.9 - 18.10: Recursion vs Iteration, Tail Recursion

• School: UCSD
• Department: Computer Science & Engineering
• Course: CSE 8B
• Professor: Yingjun Cao

Document Summary

Recursion == alternate form of program control. Loops require a loop body and loop control structure. Recursion requires a selection statement (base case) to know whether or not to call the method recursively. Any recursive problem can be solved recursively. Tail recursive method is efficient for reducing stack size. No operations to be performed on return from a recursive call method is tail recursive. Example of a tail recursive method public static boolean ispalindrome(string s) { if(s. length() <= 1) // base case return true; else if(s. charat(0) != s. charat(s. length() 1)) // base case return false; else return ispalindrome(s. substring(1, s. length() 1)); This is a tail recursive method because no more operation are performed on the return to the recursive call. Example of a non-tail recursive method public static long factorial(int n) { if(n == 0) // base case return 1; else return n * factorial(n 1) // pending operation.