Friday, April 10, 2009

A Power of Two in a Recursive Function

Here's a table that represents the sequence of power two raised to a sequence of integers
power    2 raise to power
------   ---------------
19           524,288
18           262,144
17           131,072
16            65,536
15            32,768
14            16,384
13             8,192
12             4,096
11             2,048
10             1,024
9               512
8               256
7               128
6                64
5                32
4                16
3                 8
2                 4
1                 2
0                 1
Now, given a number, say 42. Looking at the list, we first find the first product (2 raise to power) that is less than 42, which is 32, and get the difference (42-32=10). Now we find the first number that is less than 10, which is 8 and get the difference (10-8=2). We keep doing it until the difference becomes zero.
Let's say the number is 511. The sequence would be 511-256=255-128=127-64=63; then 63-32=31-16=15-8=7-4=3-2=1-1=0.
I created a recursive function returning the sequence of integers that served as exponents in the power of two series (make sense?). So in the first sample, 42 should return the list 32, 8, 2. In the second sample, 511 should return the list, 256, 128, 64, 32, 16, 8, 4, 2, 1 Here's the function I created:
create function GetSeries(@intVar int)
returns @t table (seqn int, series int)
as
begin

declare @seqn int, @series int

select top 1 @seqn = seqn, @series = power(2, seqn) from
(select top 20 seqn = (select count(*)
            from sysobjects b where a.id > b.id)
from sysobjects a) seqnkey
where power(2, seqn) <= @intVar order by 1 desc   set @intVar = @intVar - @series    if @intVar > 0
insert into @t (seqn, series)
select @seqn, @series
union
select * from dbo.GetSeries(@intVar)
else
insert into @t (seqn, series)
select isnull(@seqn,0), isnull(@series, power(2, 0))
return
end
Here's the sample output:
select * from GetSeries(42)
order by series desc
Here's the resultset:
seqn     series
----     ------
5         32
3          8
1          2
This may be a simple function, but there are a number of application that can use this. Also, this is a good sample of a recursive function.


~~ CK

No comments:

Post a Comment