SitePoint Sponsor

User Tag List

Results 1 to 3 of 3
  1. #1
    SitePoint Zealot
    Join Date
    Oct 2006
    Posts
    153
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Recursive function apparently violates if curly brace behavior. Please explain?

    Hello
    I have been reading the book "JavaScript: The Good Parts" and have found some example code that confuses me. The code gives you the solution to the Hanoi puzzle. It uses a recursive function and an if statement within the recursive function. If the if statement is true the function calls it self and most of the curly brace body of the if statement is ignored. However if the if statement fails it appears you execute statements within the body of the if statement curly braces in Spite of the fact that the if statement fails. I am saying this because I have checked out this code by both stepping through it with the Firerbug Firefox extension and using the alert statement approach and both seem to yield the fact that when the if statement fails instead of bypassing the entire code within the curly braces you execute the next statement after the recursive call. I am confused. Could you help? The code I am talking about is below.
    Code:
    var hanoi = function (disc, src, aux, dst) {
        if (disc > 0) {
            hanoi(disc - 1, src, dst, aux);
            document.writeln('Move disc ' + disc +
                    ' from ' + src + ' to ' + dst);
             hanoi(disc - 1, aux, src, dst);
        }
    }
    
    hanoi(3, 'Src', 'Aux', 'Dst');
    Last edited by MarcMiller; Oct 4, 2008 at 07:56. Reason: spelling

  2. #2
    SitePoint Guru
    Join Date
    Apr 2006
    Posts
    802
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Make the function a little easier to work with-
    give it a temporary global instead of document.write,
    and have it call itself once instead of twice per iteration.

    when this makes sense to you, the original should be obvious.

    Code:
    var hanoi = function (disc, src, aux, dst){
    	if (disc > 0){
    		hanoi_text+='\nMove disc ' + disc + ' from ' + src + ' to '+ dst;
    		hanoi(disc - 1, aux, src, dst);
    	}
    }
    //test sample
    window.hanoi_text='';
    Code:
    hanoi(3,'Src', 'Aux', 'Dst');
    alert(hanoi_text);
    hanoi_text=undefined;
    Last edited by mrhoo; Oct 5, 2008 at 14:37.

  3. #3
    SitePoint Evangelist
    Join Date
    Jul 2007
    Posts
    345
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    If the if test condition is true, all of the block is executed.
    1) The hanoi function is called with one less disc
    2) The document.writeln function is called
    3) The hanoi function is called again with one less disc and re-ordered arguments

    The recursion works, i.e. it terminates, because the calls to hanoi eventually have disc = 0 as the first parameter. The if test fails and the hanoi function returns. The program then comes back up through each called hanoi function, letting them complete their blocks.

    E.g. If your were to call hanoi with the number of discs hard-coded, it might look like
    Code:
    hanoi(2, ...) {
       hanoi(1, ...) {
          hanoi(0, ...) {
             // does nothing
          }
          document.writeln(...);
          hanoi(0, ...) {
             // does nothing
          }
       }
       document.writeln(...);
       hanoi(1, ...) {
          hanoi(0, ...) {
             // does nothing
          }
          document.writeln(...);
          hanoi(0, ...) {
             // does nothing
          }
       }
    }


Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •