SitePoint Sponsor

User Tag List

Results 1 to 2 of 2
  1. #1
    SitePoint Wizard megamanXplosion's Avatar
    Join Date
    Jan 2004
    Location
    Kentucky, USA
    Posts
    1,099
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Recursion Gone Wild

    I have been learning the paradigm of functional programming recently. For the most part, things have been going well. The hardest part has been to learn how to use recursion instead of the usual 'for' and 'while' loops that are common to imperative programming. I wanted something simple to start with, so I decided to write a recursive function that would return an array of numerical values by counting up to some number according to some stepping size. For example, cons(10, 1) would return array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) and cons(10, 2) would return array(2, 4, 6, 8, 10).

    About 24 hours ago, I wrote that function and I tested it by calling cons(10, 1), cons(10,2), cons(10,4), etc. and it behaved as expected, so I thought my goal had been accomplished, but it dawned on me a little while ago that the function is wonky when it comes to step sizes of 3 and 6 (and I presume other multiples of 3). I know the function is behaving wrongly, but the code looks correct to me, so I am stumped as to what the problem could be. Here is the code for the function and a few calls that print the resulting list to the screen:

    Code PHP:
    <?php
     
    	function cons($number, $step = 1, $list = array()) 
    	{
    		if ($number > 0)
    		{
    			$list = cons($number-$step, $step); 
    			$list[] = $number;
    		}
    		return $list;
    	}
     
    	$list1 = cons(20, 1); echo '<pre>$list1 == ', print_r($list1, true), '</pre>';
    	$list2 = cons(20, 2); echo '<pre>$list2 == ', print_r($list2, true), '</pre>';
    	$list3 = cons(20, 3); echo '<pre>$list3 == ', print_r($list3, true), '</pre>';
    	$list4 = cons(20, 4); echo '<pre>$list4 == ', print_r($list4, true), '</pre>';
    	$list5 = cons(20, 5); echo '<pre>$list5 == ', print_r($list5, true), '</pre>';
    	$list6 = cons(20, 6); echo '<pre>$list6 == ', print_r($list6, true), '</pre>';
     
    ?>

    Look at the results of $list3 and $list6. The numbers in the array increase according to the stepping size that I passed into the function, but the arrays both begin with the number 2, instead of the 3 and 6 that I had expected. Can someone please enlighten me as to why this is happening and what could be done to fix it?

  2. #2
    SitePoint Wizard megamanXplosion's Avatar
    Join Date
    Jan 2004
    Location
    Kentucky, USA
    Posts
    1,099
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    It's just my luck that I would figure out the source of the problem right after posting my question. According to my code, the cons function keeps calling itself with the specified stepping size until it reaches zero and then it returns, returns, returns. It's going backwards. cons(20,3) counts 20, 17, 14, 11, 8, 5, 2, and then returns again and again to produce 2, 5, 8, etc. The same reasoning applies to cons(20,6), which counts from 20, 14, 8, 2 and then returns again and again to produce 2, 8, 14, 20. This is the source of those (now not-so) mysterious 2s. I need to count up to the specified number from zero, not down from the specified number to zero.

    Hindsight is 20/20, I suppose. I haven't figured out how to count the other way yet, but I have only been thinking about it for a minute or so. If I have any prolonged trouble in figuring out how to do it, I will bump this thread with a request for help. For now, however, I think I will be fine ^_^


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
  •