Different ways to solve a problem

  • Some problem that was solved with recursion, can also be solved with a loop

  • Example:

      • We solved the palindrome problem with a for-loop here:

      • We solved the palindrome problem with recursion here:

  • $64,000 question:

    • Are there any difference in these solutions ?

    Short answer:

      • Yes:   recursion uses a lot more memory space

Overhead in a loop-statement

  • Consider the isPalindrome( ) method that uses a loop to determine if a string is a palindrome: 

        public static boolean isPalindrome(String w)
    {
        boolean isPalindrome = true;
        int i, last;
      
        last = w.length() - 1;

        for ( i = 0; i < w.length()/2; i++ )
        {
            if ( w.charAt( i ) != w.charAt( last-i ) )
            {
                isPalindrome = false;
                break; // We can exit the loop now
            }
        } 
	return isPalindrome;
    }

  • Notice that:   the variables inside the method are defined just once.

DEMO: demo/07-recursion/06-recursion-vs-iteration/IterativePalin.java       Step in BlueJ

Overhead in recursion

  • Consider the isPalindrome( ) method that uses a recursion to determine if a string is a palindrome: 

        public static boolean isPalindrome(String w)
    {
        boolean helpSol;
        boolean mySol;

        if ( w.length() <= 1 )
        {  // base cases
           return true;
        }
        else
        {
           int lastPos = w.length() - 1;
           helpSol = isPalindrome( w.substring(1, lastPos) );

	   mySol = (w.charAt(0) == w.charAt(lastPos)) && helpSol;
	   return mySol;
        }
    }

  • Notice that:   each recursive call will create new (= more) variables

DEMO: demo/07-recursion/06-recursion-vs-iteration/RecursivePalin.java       Step in BlueJ

Which technique should you use ?

  • Recursion has some negative aspects:

      • It uses up a lot of memory.          

  • So why, then, would we use recursion ?

      • Recursion enables you to construct a clear, simple solution for recursive problem

        Example: the Tower of Hanoi

        (It is very difficult to solve the Tower of Hanoi without using recursion !)

  • The decision whether to use recursion or iteration should be based on the nature of, and your understanding of, the problem you are trying to solve.

  • The rule of thumb is:   to use whichever approach can best develop an intuitive (= simple) solution that naturally mirrors the problem.